문제 설명
이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
입력 조건
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.
출력 조건
입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.
틀린 코드 (27% 쯤 틀림)
import sys
sys.setrecursionlimit(10 ** 5)
pre_order = []
while True:
try:
number = int(sys.stdin.readline().rstrip())
pre_order.append(number)
except:
break
post_order = []
# 루트 바로 아래 레벨의 왼쪽 자식과 오른쪽 자식을 구한다.
left_idx = 1 if len(pre_order) > 1 else -1
right_idx = -1
for i in range(1, len(pre_order)):
if pre_order[i] >= pre_order[0]:
right_idx = i
break
# 현재 기준 노드 값, 왼쪽 범위 배열, 오른쪽 범위 배열
def make_post_order(current: int, left: list, right: list):
global post_order
# 리프 노드일 경우 끝
if len(left) == 0 and len(right) == 0:
return
else:
if len(left): # 왼쪽 자식이 있다면, 왼쪽 범위 배열에서 다시 왼쪽과 오른쪽으로 나눈다.
left_node = left[0]
left_right = -1
for k in range(1, len(left)):
if left_node < left[k]:
left_right = k
break
if left_right != -1:
make_post_order(left_node, left[1:left_right], left[left_right:])
else:
make_post_order(left_node, left[1:], [])
post_order.append(left_node)
if len(right): # 오른쪽 자식이 있다면, 오른쪽 범위 배열에서 다시 왼쪽과 오른쪽으로 나눈다.
right_node = right[0]
right_right = -1
for k in range(1, len(right)):
if right_node < right[k]:
right_right = k
break
if right_right != -1:
make_post_order(right_node, right[1:right_right], right[right_right:])
else:
make_post_order(right_node, right[1:], [])
post_order.append(right_node)
# 루트 노드 1개만 있는 트리일 경우, 바로 전위 순회 결과를 그대로 출력
if left_idx == -1 and right_idx == -1:
for number in pre_order:
print(number)
else:
make_post_order(pre_order[0], pre_order[1:right_idx], pre_order[right_idx:])
# 후위 순회는 가장 마지막이 루트 노드
post_order.append(pre_order[0])
for number in post_order:
print(number)
반례
7
6
5
4
3
2
1올바른 답 (expected)
1
2
3
4
5
6
7출력 결과 (actual)
2
3
4
5
6
1
7맞힌 코드
import sys
sys.setrecursionlimit(10 ** 5)
pre_order = []
while True:
try:
number = int(sys.stdin.readline().rstrip())
pre_order.append(number)
except:
break
post_order = []
# 루트 바로 아래 레벨의 왼쪽 자식과 오른쪽 자식을 구한다.
left_idx = 1 if len(pre_order) > 1 else -1
right_idx = -1
for i in range(1, len(pre_order)):
if pre_order[i] >= pre_order[0]:
right_idx = i
break
# 현재 기준 노드 값, 왼쪽 범위 배열, 오른쪽 범위 배열
def make_post_order(current: int, left: list, right: list):
global post_order
# 리프 노드일 경우 끝
if len(left) == 0 and len(right) == 0:
return
else:
if len(left): # 왼쪽 자식이 있다면, 왼쪽 범위 배열에서 다시 왼쪽과 오른쪽으로 나눈다.
left_node = left[0]
left_right = -1
for k in range(1, len(left)):
if left_node < left[k]:
left_right = k
break
if left_right != -1:
make_post_order(left_node, left[1:left_right], left[left_right:])
else:
make_post_order(left_node, left[1:], [])
post_order.append(left_node)
if len(right): # 오른쪽 자식이 있다면, 오른쪽 범위 배열에서 다시 왼쪽과 오른쪽으로 나눈다.
right_node = right[0]
right_right = -1
for k in range(1, len(right)):
if right_node < right[k]:
right_right = k
break
if right_right != -1:
make_post_order(right_node, right[1:right_right], right[right_right:])
else:
make_post_order(right_node, right[1:], [])
post_order.append(right_node)
# 루트 노드 1개만 있는 트리일 경우, 바로 전위 순회 결과를 그대로 출력
if left_idx == -1 and right_idx == -1:
for number in pre_order:
print(number)
else:
if right_idx != -1:
make_post_order(pre_order[0], pre_order[1:right_idx], pre_order[right_idx:])
else:
make_post_order(pre_order[0], pre_order[1:], [])
# 후위 순회는 가장 마지막이 루트 노드
post_order.append(pre_order[0])
for number in post_order:
print(number)
처음에 루트 노드를 호출할 때도 오른쪽 서브 트리 루트가 있느냐 아니냐를 나눠서 호출했다.
else:
if right_idx != -1:
make_post_order(pre_order[0], pre_order[1:right_idx], pre_order[right_idx:])
else:
make_post_order(pre_order[0], pre_order[1:], [])
# 후위 순회는 가장 마지막이 루트 노드
post_order.append(pre_order[0])
for number in post_order:
print(number)최적화된 코드 (참고)
import sys
sys.setrecursionlimit(10 ** 5)
pre_order = []
while True:
try:
number = int(sys.stdin.readline().rstrip())
pre_order.append(number)
except:
break
# 시작 인덱스, 끝 인덱스
def make_post_order(start: int, end: int):
global pre_order
# 범위 넘어서면 리프 노드의 자식, 즉 null에 접근 한 것이므로 기저 조건
if start > end:
return
else:
# 현재 기준에서 루트 노드는 가장 첫 번째 순서
current_root = pre_order[start]
# 현재 기준 루트노드보다 처음으로 큰 값이 오른쪽 서브 트리의 루트가 된다.
right_index = start + 1
# start + 1 (현재 기준 루트노드 바로 다음 인덱스) ~ end (끝 인덱스) 까지 확인해본다.
for k in range(start + 1, end + 1):
if current_root < pre_order[k]:
right_index = k
break
# 왼쪽 서브 트리
make_post_order(start + 1, right_index - 1)
# 오른쪽 서브 트리
make_post_order(right_index, end)
# 다 분할하고 나서 마지막에 루트를 출력해주면 된다. (왼 -> 오-> 루트 이기 때문)
print(current_root)
make_post_order(0, len(pre_order) - 1)
내가 직접 푼 코드보다 약 400ms 정도 빠르다.
직접 푼 것은 파라미터가 슬라이싱된 배열이기 때문에 슬라이싱 크기만큼 시간 복잡도가 추가적으로 걸린다. 반면 참고한 코드는 인덱스가 파라미터라서 해당 작업이 필요 없다.
아키텍쳐 설계와 테스트 코드에 관심이 많음.