junhwa100 님의 블로그

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:..

1. 문제 이해단방향 Linked List의 헤드가 주어진다.Linked List를 뒤집고 뒤집힌 Linked List의 헤드를 리턴한다.  2. 풀이 과정Linked List를 뒤집으려면 각 노드의 next 포인터가 이전 노드를 가리키도록 바꿔야 한다. 현재 노드(node)와 이전 노드(prev)를 각각 head와 None으로 초기화한다.prev는 뒤집힌 Linked List에서 node의 next가 가리킬 노드이다. node의 next를 next 변수에 임시로 저장한다. node의 next를 prev로 변경하여 연결을 역전한다. prev를 node로, node를 next로 업데이트한다.while node: next, node.next = node.next, prev prev, node = ..

1. 문제 이해Linked List의 헤드가 주어진다.중간 노드를 삭제하고, 수정된 Linked List의 헤드를 리턴한다.Linked List의 크기가 n일 때, 중간 노드는 0부터 시작하는 인덱스를 기준으로 [n/2]번째 노드이다.([x]는 x보다 작거나 같은 가장 큰 정수이다.)  2. 풀이 과정Linked List의 중간 노드를 찾아야 한다.Runner 기법을 사용한다.https://junhwa100.tistory.com/11 prev, slow, fast 3개의 변수를 만든다.slow는 한 칸씩, fast는 두 칸씩 이동한다.slow, fast = head, headprev = Nonewhile fast and fast.next: prev = slow slow = slow.next ..

1. 문제 이해Dota2의 세계에는 Radiant와 Dire라는 두 진영이 존재한다. Dota2 상원은 이 두 진영에서 온 상원 의원들로 구성되어 있다. 이제 상원은 Dota2 게임의 변경 사항에 대해 결정하려고 한다.  이 변경 사항에 대한 투표는 라운드 기반 절차로 진행된다. 각 라운드에서, 각 상원 의원은 다음 두 가지 권한 중 하나를 행사할 수 있다. 1. 상대방 의원의 권한 박탈: 한 상원 의원은 다른 상원 의원이 이 라운드와 모든 이후 라운드에서 모든 권한을 잃도록 만들 수 있다. 2. 승리 선언: 만약 이 상원 의원이 권리를 가진 모든 상원 의원이 같은 진영에 속해 있음을 발견하면, 그는 승리를 선언하고 게임 변경 사항을 결정할 수 있다. 문자열 senate가 주어진다. 이 문자열은 각 상원..

1. 문제 이해RecentCounter 클래스를 구현한다.RecentCounter 클래스는 특정 시간 범위 내에서 최근 요청의 수를 계산한다.최근 요청이 0개인 상태로 카운터를 초기화한다.int ping(int t) 함수는 시간 t에 새로운 요청을 추가하고, 지난 3000밀리초 동안 발생한 요청 수를 리턴한다.구체적으로는 [t - 3000, t] 범위 내에서 발생한 요청의 수를 리턴한다.(ping 함수의 각 호출은 이전 호출보다 항상 더 큰 값을 갖는 t를 사용한다.)이해하기 어렵다..  2. 풀이 과정범위 밖에 있는 오래된 요청들은 제외한다. 큐를 사용한다. 클래스가 호출될 때, 큐를 초기화한다.def __init__(self): self.requests = deque() 새로운 요청을 큐에 추가..

1. 문제 이해주어진 인코딩된 문자열을 디코딩하여 리턴한다.인코딩된 문자열은 k[encoded_string] 형태로, 대괄호 안의 encoded_string을 정확히 k번 반복하여 디코딩한다.  2. 풀이 과정스택을 사용한다.for문을 통해 문자열을 조회한다.만약 해당 문자가 ']'가 아니라면 스택에 문자를 추가한다.만약 해당 문자가 ']'라면 '['를 찾을 때까지 스택에서 문자를 꺼낸다.이때 임시 리스트를 만들어 꺼낸 문자들을 저장한다.저장한 문자를 스택 최상단에 있는 숫자만큼 반복해서 다시 스택에 저장한다.class Solution: def decodeString(self, s: str) -> str: stack = [] for i in range(len(s)): ..