라이브코테 준비 - 연습문제3
어떤 기업의 라이브코테를 봐야했다.
메일로 연습문제를 보내줬으므로 풀어보도록 하였다. 마지막이다.
문제
애플에서 출제된 문제입니다.
주어진 이진 트리에서, 루트 (최상위 노드) 에서 리프 (자식이 없는 최하위 노드) 까지의 경로를 모두 더하였을 떄 가장 작은 값을 갖는 경로를 찾고, 그 합을 반환하세요.
예를 들어, 이 트리에서 최소 값을 갖는 경로는 [10, 5, 1, -1] 이며, 그 합인 15를 반환해야 합니다.
1
2
3
4
5
6
7
10
/ \
5 5
\ \
2 1
/
-1
테스트 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def test_p135_1():
node = Node(10)
assert(min_path_sum(node) == 10)
def test_p135_2():
node = Node(10, Node(5), Node(5))
assert(min_path_sum(node) == 15)
def test_p135_3():
node = Node(10, Node(5, None, Node(2)), Node(5))
assert(min_path_sum(node) == 15)
def test_p135_4():
node = Node(10, Node(5, None, Node(2)), Node(5, None, Node(1)))
assert(min_path_sum(node) == 16)
def test_p135_5():
node = Node(10, Node(5, None, Node(2)), Node(5, None, Node(1, Node(-1), None)))
assert(min_path_sum(node) == 15)
풀이
노드를 선언해야하는데, 테스트코드를 잘 보면 왼쪽 노드와 오른쪽 노드를 한 번에 초기화 받는다. 안 받을 수도 있으므로 디폴트값도 지정해줘야한다.
1
2
3
4
5
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
left와 right모두 Node형태의 클래스가 들어오거나 None 값이 들어올 것이다.
테스트코드에서 min_path_sum(node)를 통해 최소값을 찾고 int형으로 값을 비교하므로 인자와, 리턴 타입은 정해졌다. 메소스이름까지도. 메소드 시그니처가 완성되었으므로 내부 로직만 작성하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def min_path_sum(node: Node) -> int:
result = float('inf')
dq = deque()
dq.append((node, node.value))
while dq:
node, value = dq.popleft()
if node.left:
node.left.value += node.value
dq.append((node.left, node.left.value))
if node.right:
node.right.value += node.value
dq.append((node.right, node.right.value))
if not node.left and not node.right:
result = min(result, value)
return result
나는 그래고 pop()연산이 배열보다 빠른 deque를 사용하여 작성하였다. 최솟값을 구해야하므로 float('int')를 통해 max값을 설정해준다.
BFS방식으로 노드들을 탐색할 것이기에 while문을 돌기전에는 초기값으로 맨 처음 들어온 노드와, 그 value를 넣는다.
탐색하면서 탐색하는 노드들에 누적합을 저장할 것이고(1번만 방문할 것이므로 상관없음.), 만약 리프노드에 들어갔다면(자식이 없음) 여태 더해진 누적합과 최솟값을 비교하여 갱신해준다.
그리고 리턴하면 된다.
결론
이런 문제는 예외상황이 거의 없다고 보면된다. 그렇기에 이대로 작성해도 될 것 같다.
참고로 나와 답지는 꽤나 다른 부분이 있다. 하지만 로직은 같다고 생각하여.. 굳이 수정하지 않았다.