LeetCode 2196 Create Binary Tree From Descriptions 접근 map의 key에 node.val, value에 node reference 가 담긴다. 부모 노드는 p[child] = parent 의 방식으로 저장하여 루트를 찾는다. descriptions 를 훑으며 map 에 이미 저장된 child 가 있다면 해당 child 를 적절한 left or right 에 연결하고, child 가 map 에 없다면 새로운 노드를 만들어 연결한다. 사고 리스트로 풀어도 되고, 맵으로 풀어도 된다. 공간 덜 쓰고 root 찾는 방법이 있을것도 같다. map 을 안쓰고는 (node 들의 reference 를 다 붙잡고 있지 않고는) tree 만들 방법이 없는거겠지? ...
접근 정렬되어 있는 array 의 처음과 끝에 포인터를 둔다. target 과 비교하며 포인터를 움직인다. 사고 정렬되어 있고, 답이 하나로 보장되어 있다길래 two pointer 썼다. class Solution: def twoSum(self, numbers: list[int], target: int) -> list[int]: i, e = 0, len(numbers) - 1 while i < e: if numbers[i] + numbers[e] == target: return [i + 1, e + 1] elif numbers[i] + numbers[e] > target: e -= 1 else: i += 1
사고 같은 크기의 matrix 에 0, 0 부터 현재 index 까지 만들어지는 사각형 sum 을 저장하는 방식이 쉬우면서도 효율적인 접근이다. 왜인지 모르겠으나 불필요한 operation 이 포함된다고 생각해서 나는 같은 크기의 matrix 에 같은 row 에 있는 현재까지의 column sum 을 저장했다. 결론적으로 첫번째 접근보다 비효율적이다. 긴 row 에는 dp 에 여러번 접근해야할뿐더러 row 가 길수록 col1 을 빼주는 operation 을 많이 하게 된다. class NumMatrix: mat = None def __init__(self, matrix: list[list[int]]): self.mat = [[0] * len(matrix[0]) for _ in range(len(matrix))] for r in range(len(matrix)): self.mat[r][0] = matrix[r][0] for c in range(1, len(matrix[0])): self.mat[r][c] = self.mat[r][c - 1] + matrix[r][c] def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int: blk = 0 for r in range(row1, row2 + 1): blk += self.mat[r][col2] blk -= self.mat[r][col1 - 1] if col1 > 0 else 0 return blk
접근 전체 node 가 head를 제외하고 n개일 때 head 에서 왼쪽에 k, 오른쪽에 n-k 만큼의 node를 갖는 경우의 수는 dp[k] * dp[n - k] 이다. 경우의 수를 곱해서 찾기 때문에 dp[0] 은 1로 둔다. 사고 예제 그림에서 보듯이 가능한 현재 경우의 수는 이전의 경우의 수 전체를 왼쪽 subtree, 오른쪽 subtree 로 갖는 경우로 생각해서 dp[i - 1] * 2 + ? 으로 시작했다. 이건 왼쪽에 dp[n - 1] 개, 오른쪽 0 그리고 오른쪽 dp[n - 1], 왼쪽 0 개를 가지는 하나의 케이스라고 생각했다. 그래서 모든 경우의 수를 수도코드로 생각하고 아래와 같이 구현했다. ...
접근 dp 는 s의 현재 index를 단어의 끝으로 가장 길게 완성할 수 있는 시작 index를 가리킨다. 각 스트링 인덱스 i 마다 0부터 i까지 loop 돌며 딕셔너리에 있는지 확인한다. 딕셔너리에 있다면 그 앞선 단어와 연결되는지 확인 후 dp 업데이트 한다. i-5 ~ i 까지 이어지는 단어가 있다면 ?? ~ i-6 까지 이어진 단어가 있는지 보는식이다. 사고 처음에 dfs 로 접근하였다. 시간초과를 받고 dp 로 다시 풀었다. 시간 복잡도 O(s.length ^ 2) ...
접근 linear 로 훝으며 모든 값을 곱하며 진행한다. 메모리 절약을 위해 부호만 기록한다. 각 index 에서 여태의 곱연산 부호에 따라 조건부로 최대 부분 수열 길이를 갱신한다. 0 을 만나면 필요한 변수들 초기화한다. 사고 0은 처리해줘야 하고, 양수는 곱해져도 어딜 slicing 하는지에 따라 부호가 바뀌지 않는다. 따라서 0이 아닌 값들을 쭉 이어서 길이를 기억한다. 첫번재 음수가 나오는 인덱스를 표시해놓고 현재 pointer 까지 곱연산이 양수이면 현재 까지 이어진 값의 길이와 max 를 비교해서 값을 갱신하고 음수라면 (pointer - 첫번째 음수 인덱스) 와 max 를 비교하여 갱신한다. ...
접근 현재 pointer 와 닿을 수 있는 최대 거리인 reach, 점프 횟수 카운트, 새로운 reach 후보 변수인 temp 네 가지 변수를 이용한다. 닿는 index 중 가장 멀리까지 갈 수 있는 index 를 temp 후보와 비교해 업데이트 한다. 이제 점프할 차례 때 가장 큰 temp 값을 보장해주는 곳으로 점프하고 이전 pointer에 이어서 후보군을 탐색한다. 지금까지 본 곳 중에서는 지금 자리가 가장 멀리까지 갈 수 있다는 사실을 알기 때문이다. 따라서 pointer 가 linear 로 진행하는 것이 곧 시간복잡도 O(n) 이 되며 최적해이다. 사고 앞선 Jump Game 과 다른 점은 reach 를 계속 업데이트 하지 않고 후보군을 끝까지 탐색 후 jump++ 와 reach 변수 재지정이 이루어지는 것이다. 그렇게 뜨문 뜨문 갱신되는 reach 내에서 loop를 반복적으로 돌아준다. ...
접근 현재 pointer 와 닿을 수 있는 최대 거리인 reach 두 변수를 이용한다. 닿는 index 중 가장 멀리까지 갈 수 있는 reach 로 계속해서 업데이트 한다. reach 만 max 를 이용해 업데이트하고 pointer 는 linear 로 움직인다 O(n). 사고 먼저 최대거리로 포인터를 옮기고 진행이 불가능하면 하나씩 뒤로 무르는 backtracking 이 떠올랐다. 하지만 visit 을 체크하는 과정에서 비효율적이라는 생각이 들어 기각했다. class Solution: def canJump(self, nums: list[int]) -> bool: pointer = 0 reach = nums[pointer] if reach + 1 >= len(nums): return True while pointer < reach: pointer += 1 reach = max(reach, pointer + nums[pointer]) if reach + 1 >= len(nums): return True return False
접근 처음과 마지막이 접하기 때문에 House Robber I 과 다른 방식을 생각해야한다. 첫번째 집을 털면 마지막 집은 고려할 필요가 없다. 그래서 0, len(배열) - 1 과 1, len(배열) 로 자른 두개의 배열에 단순하게 접근하면 된다. 사고 한참 예전에 이와 비슷한 cycle 이 있는 배열 dp 문제를 풀었는데 그보다 시간이 지난 뒤에 못 풀어서 당황했던 기억이 있다. 그 당시엔 아마 배열 마지막 집 전까지 dp 업데이트 후 첫번째 집과 마지막 집 value 를 비교했던것 같은데, 위험한 접근이고 edge case 도 매우 많았을 거라 생각된다. ...