junhwa100 님의 블로그

1. 문제 이해nums1과 nums2라는 감소하지 않는 정수 배열이 주어진다.m, n은 각각 nums1과 nums2 배열의 원소의 수를 나타낸다. nums1과 nums2를 감소하지 않는 하나의 배열로 merge해야 한다.merge한 배열을 nums1에 저장한 뒤 nums1을 리턴한다. 2. 풀이 과정추가적인 공간 사용 없이 nums1에 저장해야 한다.어떻게 구현할 수 있을까? 투 포인터를 사용하여 배열의 뒤쪽부터 값을 채워 넣는다. 우선 세 개의 포인터를 각 배열의 가장 끝으로 설정한다.p1 = m - 1p2 = n - 1write_idx = m + n -1 nums2의 모든 요소가 nums1으로 넘어갈 때까지 반복한다.매 반복마다 두 배열의 현재 포인터가 가리키는 값을 비교하여 더 큰 값을 nums1..

1. 문제 이해SmallestInfiniteSet 클래스를 구현한다. SmallestInfiniteSet 객체를 모든 양의 정수를 포함한 상태로 초기화한다. int popSmallest(): 집합에 포함된 가장 작은 정수를 제거하고 리턴한다. void addBack(int num): 양의 정수 num을 집합에 다시 추가한다. 단, 이미 집합에 있는 경우에는 추가하지 않는다. 2. 풀이 과정무한한 모든 양의 정수를 메모리에 저장할 수 없다.다음에 꺼낼 작은 수만 관리한다. 필요할 때마다 꺼낸다.다음에 꺼낼 수를 나타내는 self.current를 만든다.addBack으로 다시 추가된 숫자들을 저장하는 heap을 만든다.addBack으로 숫자를 추가할 때 중복을 막기 위한 set도 만든다.def __init..

1. 문제 이해이진 탐색 트리(BST)와 정수 val이 주어진다.노드의 값이 val고 같은 노드를 찾아 해당 노드를 루트로 하는 서브트리를 리턴한다.그런 노드가 존재하지 않으면 null을 리턴한다.  2. 풀이 과정현재 노드 변수(cur_node)를 만들고 루트로 초기화한다. 현재 노드 값이 val과 다를 때까지 반복한다.현재 노드 값이 val보다 크다면 현재 노드를 왼쪽 자식으로 이동시킨다.현재 노드 값이 val보다 작다면 현재 노드를 오른쪽 자식으로 이동시킨다. 반복문이 끝나면 현재 노드를 리턴한다.  3. 전체 코드class Solution: def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: ..

1. 문제 이해이진 트리가 주어진다.루트의 레벨은 1, 그 자식들의 레벨은 2 ... 이렇게 정의된다.모든 노드 값의 합이 최대가 되는 레벨 x를 리턴한다.  2. 풀이 과정BFS로 트리를 순회한다.BFS는 통상적으로 큐를 이용한 반복 구조를 활용한다 트리를 순회하면서 같은 레벨의 노드 값들의 합을 구한다. 노드들의 합이 최대인 레벨을 리턴한다. 큐에 노드가 남아 있는 동안 반복한다.그리고 현재 큐의 길이만큼 반복하여 현재 레벨의 모든 노드를 처리한다.현재 레벨 노드들의 합이 최대라면 정답 변수를 현재 레벨로 설정한다.while queue: cur_sum = 0 for _ in range(len(queue)): cur_root = queue.popleft() cur_s..

1. 문제 이해이진 트리가 주어진다.이때 트리의 오른쪽에 서 있다고 상상한다.위에서부터 아래까지 볼 수 있는 노드들의 값을 순서대로 리턴한다.  2. 풀이 과정BFS로 트리를 순회한다.트리의 다음 레벨로 넘어가기 전 마지막 노드의 값을 저장한다. BFS는 통상적으로 큐를 이용한 반복 구조를 활용한다.큐에 root를 넣고 초기화한다.queue = collections.deque([root]) 큐에 노드가 남아 있는 동안 반복한다.반복될 때마다 큐의 가장 오른쪽 노드의 값을 결과 리스트에 추가한다.(=트리의 현재 레벨의 가장 오른쪽 값)그리고 현재 큐의 길이만큼 반복하여 현재 레벨의 모든 노드를 처리한다. 큐에서 왼쪽부터 노드 하나를 꺼낸다.꺼낸 노드의 왼쪽, 오른쪽 자식이 있는지 확인하고 있다면 큐에 추가..

1. 문제 이해이진 트리가 주어진다.트리의 노드 p, q의 Lowest Common Ancestor(LCA)를 리턴한다.LCA는 두 노드 p, q의 공통 조상 가장 낮은(가까운) 노드이다.(한 노드가 자기 자신을 자신의 자손으로 간주하는 것을 허용한다.)  2. 풀이 과정dfs를 사용해서 p, q를 만날 때까지의 경로를 각각 저장해 p, q와 가장 가까운 공통 노드를 찾는다.일종의 LIFO 개념이므로 경로를 저장할 때, 스택을 사용한다. stack과 p, q별 경로를 저장할 딕셔너리 paths를 전역적으로 생성한다.stack = []paths = {} dfs의 매개변수로 현재 노드와 target 노드를 전달한다.만약 노드가 없다면 False를 리턴한다.현재 노드를 스택에 추가한다.def dfs(node,..

1. 문제 이해이진 트리가 주어진다.주어진 트리에서 가장 긴 "지그재그 경로"의 길이를 리턴한다.("지그재그 경로"는 방문한 노드 수 - 1로 정의된다. 노드의 수가 아니라 경로의 수이다.)  2. 풀이 과정dfs 매개변수로 방향(왼쪽, 오른쪽), 경로의 길이를 전달한다.(현재 노드에서 나가는 방향이다.)만약 노드가 없다면 경로의 길이 - 1을 리턴한다.def dfs(node, direction, length): if not node: return length - 1 현재 매개변수에 맞춰 양 방향으로 가는 경로의 길이를 재귀적으로 계산한다.만약 방향이 전환된다면, dfs 매개변수의 경로의 길이를 1 증가시킨다. 그렇지 않다면 경로의 길이를 1로 초기화한다.if direction == '..

1. 문제 이해이진 트리와 정수 targetSum이 주어진다.경로의 값들의 합이 targetSum인 경로의 개수를 리턴한다.(경로는 루트에서 시작하거나 리프에서 끝날 필요 없다. 반드시 아래쪽으로만 이동한다.)  2. 풀이 과정아래쪽으로만 이동해야 하므로 dfs를 사용한다.하지만 모든 노드를 루트로 삼아 dfs를 호출하면 동일한 하위 경로를 여러 번 계산하게 된다. O(n^2)에 가까워진다. 누적 합(prefix sum) 아이디어를 도입한다.이전에 계산된 누적 합 중, targetSum만큼 떨어진 값을 찾는다.현재까지의 누적 합, cur_sum이 있을 때, cur_sum - targetSum이 등장한 횟수를 확인하면 해당 경로에서 targetSum을 만족하는 경로가 몇 개인지 알 수 있다. 해시맵 pre..

1. 문제 이해하나의 이진 트리가 주어진다.트리의 노드 X는 루트에서 X까지의 경로에서 X보다 값이 큰 노드가 없는 경우 "좋은 노드"라 불린다.주어진 트리의 "좋은 노드" 개수를 리턴한다.  2. 풀이 과정dfs를 사용해서 노드들을 탐색한다.어떻게 경로의 최댓값과 현재 노드의 값을 비교할까? 경로의 최댓값은 경로에 따라 값이 달라지는 동적인 값이다.각 경로에서 독립적으로 최댓값을 유지하기 위해 최댓값을 dfs의 매개변수로 전달한다. 현재 노드의 값이 경로의 최댓값보다 크거나 같다면 "좋은 노드"로 판단하고 good 값을 1로 설정한다.그렇지 않다면 good 값을 0으로 설정한다.if node.val >= max_num: good = 1 else: good = 0 현재 노드까지의 경로에서 최댓..

1. 문제 이해두 개의 이진 트리가 주어진다.이진 트리의 모든 리프 노드를 왼쪽에서 오른쪽 순서로 고려하면, 이 리프 노드들의 값은 leaf value sequence를 형성한다.두 개의 이진 트리가 leaf value sequence가 동일한 경우, 두 트리는 leaf-similar하다고 간주된다.주어진 두 이진 트리가 leaf-similar한 경우 True를 리턴한다.  2. 풀이 과정트리의 모든 리프 노드를 찾아야 한다.dfs는 노드의 자식을 먼저 탐색하고 돌아오는 방식이기 때문에, 리프 노드에 도달하는 데 적합하다.트리는 일종의 재귀적인 자료구조이다.(각 노드는 자식을 가지며, 자식들 역시 독립적인 트리이기 때문이다.) 재귀를 사용해 dfs를 구현한다.  3. 전체 코드class Solution:..