[정글 알고리즘] - [중]-백준 5639 이진 검색 트리 - 골드4

문제 링크 : https://www.acmicpc.net/problem/5639

문제 요약

항목	설명
입력	이진 검색 트리의 전위 순회 결과가 줄바꿈으로 주어짐
출력	해당 트리의 후위 순회 결과 출력
핵심	BST 성질을 이용해 왼쪽 서브트리와 오른쪽 서브트리를 구분
주의	입력 개수 N이 따로 주어지지 않으므로 EOF 방식으로 입력을 받아야 함

이 문제는 트리 구조를 직접 만들지 않아도, 전위 순회 결과와 BST 성질만으로 후위 순회를 복원할 수 있습니다. [Source](https://www.acmicpc.net/problem/5639)

이 문제에서 먼저 잡아야 할 것

1. 첫 값은 항상 루트다

전위 순회는 루트 → 왼쪽 → 오른쪽 순서입니다. 따라서 어떤 구간이 들어오든 그 구간의 첫 번째 값은 무조건 루트입니다. [Source](https://www.acmicpc.net/problem/5639)

2. 정렬하면 안 된다

이 문제는 단순히 값의 크기만 보는 문제가 아닙니다. 전위 순회로 들어온 순서 자체가 트리 구조를 추론하는 핵심 정보이므로, 정렬해버리면 원래 순회 정보가 완전히 깨집니다.

3. 처음으로 루트보다 큰 값이 나오는 지점이 중요하다

BST에서는 루트보다 작은 값은 모두 왼쪽 서브트리, 큰 값은 모두 오른쪽 서브트리에 들어갑니다. 그래서 전위 순회 구간에서 처음으로 루트보다 큰 값이 나오는 위치가 오른쪽 서브트리의 시작점이 됩니다. [Source](https://www.acmicpc.net/problem/5639)

전위 순회와 후위 순회 차이

전위 순회

루트 → 왼쪽 → 오른쪽

입력으로 주어지는 정보

후위 순회

왼쪽 → 오른쪽 → 루트

우리가 출력해야 하는 정보

핵심 전환

전위 순회의 첫 값으로 루트를 찾고, BST 성질로 왼쪽/오른쪽 구간을 나눈 뒤, 왼쪽 재귀 → 오른쪽 재귀 → 루트 출력을 하면 후위 순회가 됩니다.

예제로 바로 이해하기

예시 전위 순회

50 30 24 5 28 45 98 52 60

이 예시는 문제 설명에 등장하는 대표 예시입니다. [Source](https://www.acmicpc.net/problem/5639)

1단계 : 루트 찾기

50 → 첫 값이므로 루트

2단계 : 루트보다 작은 값 / 큰 값으로 분리

루트가 50이므로,

왼쪽 서브트리

30 24 5 28 45

50보다 작은 값들

오른쪽 서브트리

98 52 60

50보다 큰 값들

포인트

실제 구현에서는 처음으로 50보다 큰 값인 98이 등장하는 위치를 찾으면 그 앞은 왼쪽, 그 뒤는 오른쪽으로 나눌 수 있습니다.

3단계 : 같은 작업을 재귀적으로 반복

root = 50 → 왼쪽 구간 재귀 → 오른쪽 구간 재귀 → 마지막에 50 출력

결국 후위 순회는 왼쪽 → 오른쪽 → 루트이기 때문에, 재귀 호출 두 번이 끝난 뒤 마지막에 루트를 출력하면 됩니다.

입력 처리에서 주의할 점

이 문제는 입력 개수 N을 먼저 주지 않습니다. 따라서 입력이 끝날 때까지 계속 읽어야 합니다. [Source](https://www.acmicpc.net/problem/5639)

백준 제출용으로 깔끔한 방식

preorder = list(map(int, sys.stdin.read().split()))

남은 입력 전체를 한 번에 읽어서 숫자 리스트로 바꾸는 방식입니다.

로컬에서 직접 실행할 때 주의

콘솔에서 실행하면서 입력이 끝났다고 생각하고 엔터만 치면, 빈 줄이 들어가서 변환 에러를 만날 수 있습니다. 이건 로직 문제라기보다 입력 종료 방식 차이 때문에 생기는 경우가 많습니다.

최종 코드

import sys
sys.setrecursionlimit(10**6)

preorder = list(map(int, sys.stdin.read().split()))

def postorder(start, end):
    if start > end:
        return

    root = preorder[start]
    mid = end + 1

    for i in range(start + 1, end + 1):
        if preorder[i] > root:
            mid = i
            break

    postorder(start + 1, mid - 1)
    postorder(mid, end)
    print(root)

postorder(0, len(preorder) - 1)

코드 핵심 설명

코드	설명
sys.setrecursionlimit(10**6)	트리가 한쪽으로 길게 치우치면 재귀 깊이가 깊어질 수 있으므로 재귀 제한을 늘려줍니다.
preorder = list(map(int, sys.stdin.read().split()))	입력 개수가 따로 없으므로 남은 입력을 전부 읽어 전위 순회 리스트로 저장합니다.
root = preorder[start]	현재 구간의 첫 값이 루트입니다. 전위 순회가 루트부터 시작하기 때문입니다. [Source](https://www.acmicpc.net/problem/5639)
mid = end + 1	기본값을 구간 끝 다음으로 잡아둡니다. 이렇게 하면 루트보다 큰 값이 하나도 없는 경우, 전체가 왼쪽 서브트리로 처리됩니다.
if preorder[i] > root:	처음으로 루트보다 큰 값이 나오면 그 지점부터 오른쪽 서브트리 시작입니다.
postorder(start + 1, mid - 1)	왼쪽 서브트리를 먼저 처리합니다.
postorder(mid, end)	오른쪽 서브트리를 처리합니다.
print(root)	마지막에 루트를 출력하면 후위 순회 순서인 왼쪽 → 오른쪽 → 루트가 완성됩니다. [Source](https://www.acmicpc.net/problem/5639)

많이 틀리는 포인트

실수	왜 틀리는가
입력을 정렬해버림	전위 순회 순서 정보가 사라져서 원래 BST 구조를 복원할 수 없습니다.
가장 큰 값을 루트라고 생각함	전위 순회에서는 항상 첫 값이 루트입니다.
처음 큰 값을 찾는 비교 방향을 반대로 씀	우리가 찾는 것은 root보다 큰 첫 값이지, 작은 값이 아닙니다.
큰 값이 없을 때 처리를 안 함	오른쪽 서브트리가 비어 있는 경우를 위해 기본값을 미리 잡아두어야 합니다.
재귀 제한을 고려하지 않음	편향 트리에서는 재귀 깊이가 깊어져 런타임 에러가 날 수 있습니다.

한 번에 정리

이 문제의 핵심 한 문장

전위 순회의 첫 값은 루트이고, 처음으로 루트보다 큰 값부터 오른쪽 서브트리라는 BST 성질을 이용해 구간을 재귀적으로 나누면 후위 순회를 만들 수 있습니다.

문제는 이진 검색 트리의 전위 순회 결과만 주어졌을 때 후위 순회 결과를 구하는 것입니다. 트리를 직접 구성하지 않아도, 전위 순회와 BST의 성질만으로 왼쪽/오른쪽 구간을 재귀적으로 나누어 해결할 수 있습니다.