[백준/파이썬] 2263번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 2263번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.
입력 요약
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
출력 요약
첫째 줄에 프리오더를 출력한다.
코드
import sys; read = sys.stdin.readline
sys.setrecursionlimit(1_000_000)
results = []
n = int(read())
in_order = list(map(int, read().split()))
in_idx = {in_order[i]: i for i in range(n)}
post_order = list(map(int, read().split()))
def insert_from_in_order(in_start, in_end, post_start, post_end):
if in_start > in_end or post_start > post_end: return
results.append(post_order[post_end])
root_idx = in_idx[post_order[post_end]]
left_size = root_idx - in_start
insert_from_in_order(in_start, root_idx - 1,
post_start, post_start + left_size - 1)
insert_from_in_order(root_idx + 1, in_end,
post_start + left_size, post_end - 1)
insert_from_in_order(0, n - 1, 0, n - 1)
print(' '.join(map(str, results)))
설명
핵심은 구현 관점에서 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기