2023 https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/
요건 제한조건이 너무 단순해서 그냥 마음가는대로 이중 반복문으로 풀수도있지만 그랬다가는 알고리즘 공부하는 의미가 없다. nums리스트에서 두개만 앞값 + 뒷값으로 문자열을 연결했을때 target이 나오면 된다.
prefix, suffix 딕셔너리를 만들어서 풀수 있는데, prefix 딕셔너리에는 앞에서 얼마만큼 만들었는지를 저장하고, suffix 딕셔너리에는 뒤에서 얼마만큼 만들었는지를 저장해둔다. nums = ["123","4","12","34"], target = "1234" 인 경우를 예로 보면
target 1234에 대해서 pre로 만들수 있는 수는 123과 12이다. 이런 경우에는 앞에서 3개, 2개가 만들어졌으므로 1234를 만들기 위해서는 뒤에서 1개, 2개만 만들수 있으면 된다. 그러므로 아래 코드에서
is_prefix인 경우에, suffix에 채워야하는 남은 만큼이 저장되어있으면 그 경우의 수만큼 정답의 갯수를 기록하는 ret에 더해준다.
class Solution:
def numOfPairs(self, nums: List[str], target: str) -> int:
prefix, suffix = {}, {}
ret = 0
for n in nums:
len_n = len(n)
len_t = len(target)
is_prefix = target.startswith(n) # 현재 n이 target의 prefix인지 체크한다.
is_suffix = target.endswith(n) # 현재 n이 target의 suffix인지 체크한다.
if is_prefix: # prefix인 경우에 suffix가 채워져서 target을 만들어줄수 있으면 그만큼 정답이다.
ret += suffix.get(len_n, 0)
if is_suffix: # suffix인 경우에 prefix 가 채워져서 target을 만들어줄수 있으면 그만큼이 정답이다.
ret += prefix.get(len_t - len_n, 0)
prefix[len_n] = prefix.get(len_n, 0) + is_prefix # prefix를 찾은만큼 기록해둔다.
suffix[len_t - len_n] = suffix.get(len_t - len_n, 0) + is_suffix # suffix를 찾은만큼 기록해둔다.
return ret
979 https://leetcode.com/problems/distribute-coins-in-binary-tree/
n개의 노드에 n개의 코인이 존재하므로 모든 노드들은 각각 1개씩의 코인을 갖고 있어야 한다. 재귀적으로 탐색을 하면서 풀어야하는데 이유는 자식값을 부모에서 받아서 사용해야 하기 때문이다.
이동거리 계산은 자식이 1개보다 코인을 더 적게 갖고 있거나 많이갖고있으면 위에서던 옆에서던 가져와야 하므로 절대값으로 이동거리를 더해준다.
부모쪽에서는 자식의 코인이 1보다 부족하면 -의 개념으로, 자식의 코인이 1보다 더 많으면 +의 개념으로 계산해서 얼만큼의 코인이 부족한지를 계속 갖고 계산한다.
from collections import deque
class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
self.ret = 0
self.inorder(root)
return self.ret
def inorder(self, node):
if not node:
return 0
l_val = self.inorder(node.left)
r_val = self.inorder(node.right)
self.ret += abs(l_val) + abs(r_val)
return node.val + l_val + r_val - 1
구글 다니는 형님이 정리를 깔끔하게 잘해주셨다.
https://leetcode.com/problems/distribute-coins-in-binary-tree/discuss/221939/C%2B%2B-with-picture-post-order-traversal
1310 https://leetcode.com/problems/xor-queries-of-a-subarray/
문제부터가 예전에 많이풀었던 prefix sum과 비슷하게 생겼고 제한이 커서 단순계산으로 풀면 안된다.
prefix sum처럼 풀되, xor은 같은 수를 한번 더 xor하면 0이 되는 성질을 이용한다. dp리스트에 i번째의 수까지 전부 xor해놓은 값을 저장한다. 이후 범위를 보고 값을 계산하는데, 시작하는 인덱스가 0보다 크면 인덱스-1범위까지의 xor한 값을 한번 더 해준다.
예로 arr = [1,3,4,8,9] 라고 하자. 내 dp리스트는 [0, 1(1), 2(1^3), 6(1^3^4), 14(1^3^4^8), 7(1^3^4^8^9)]처럼 완성된다.(처음에 0을 넣었음.)
여기서 [2, 4]범위 즉(4,8,9의 xor을 구하고자 하면..) dp[4+1](index 4까지 전체 xor한 값) ^ dp[2](index 1까지 전체 xor한 값)이 된다. 이걸 풀어서 적어보면 (1^3^4^8^9) ^ (1^3) -> (4^8^9) 가 남게 되어 이런식으로 계산이 가능하다.
class Solution:
def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
dp = [0]
for i in range(len(arr)):
dp.append(dp[i] ^ arr[i])
#print(dp)
ret = []
for q in queries:
ret.append(dp[q[0]] ^ dp[q[1]+1])
return ret