[백준] 5639번 이진 검색 트리 해설 및 풀이 (Python)

백준 5639번 이진 검색 트리

https://www.acmicpc.net/problem/5639

---

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

---

문제 유형

그래프 이론 그래프 탐색 트리 재귀

 

풀이 방법 도출

 

전위 순회는 "루트 → 왼쪽 → 오른쪽" 순서로 탐색한 결과이다.

따라서 입력의 첫 번째 값은 항상 루트 노드가 된다.

 

루트보다 작은 값들은 왼쪽 서브트리, 루트보다 큰 값들은 오른쪽 서브트리에 위치한다.

 

이를 기반으로 서브트리의 범위를 preorder[start+1 ~ end] 내에서 나눌 수 있다.

후위 순회는 "왼쪽 → 오른쪽 → 루트" 순서이다.

왼쪽 서브트리를 먼저 재귀 호출 → 오른쪽 서브트리를 재귀 호출 → 루트를 출력한다.

 

현재 탐색 범위(start > end)가 잘못되었을 경우에는 재귀를 종료한다.

 

 

시간 복잡도

• 최악의 경우 O(N²)
• 평균 O(N log N)

---

핵심 코드 삽입 및 설명

 

import sys
sys.setrecursionlimit(10**6)

# 전위 순회 결과를 저장할 리스트
preorder = []

# 빈 줄 제외하고 숫자만 추가
for line in sys.stdin:
    line = line.strip()
    if line:  # 빈 줄 무시
        preorder.append(int(line))

# 후위 순회 결과를 출력하는 함수
def dfs(start: int, end: int):
    if start > end:
        return

    root = preorder[start]

    # 루트보다 큰 값이 나오는 첫 지점
    split = end + 1
    for i in range(start + 1, end + 1):
        if preorder[i] > root:
            split = i
            break

    dfs(start + 1, split - 1)  # 왼쪽 서브트리
    dfs(split, end)            # 오른쪽 서브트리
    print(root)                # 루트 출력

# 실행
dfs(0, len(preorder) - 1)