[BOJ] 2263 트리의 순회 (C/C++)

2263번: 트리의 순회

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

---

문제를 얼핏 보고 지나갔을 때에는 출력이 pre-order만 출력하는 문제인 줄 알고 너무 쉽지 않나 했었다. 알고 보니 그리 간단한 문제는 아니었다.

문제를 풀기 위해서는 입력으로 들어오는 in-order와 post-order의 성질을 알아야 한다. 우선 post-order는 루트 노드가 제일 마지막에 출력되는 특징이 있다. 그리고 in-order의 경우에는 루트 노드를 기준으로 왼쪽은 왼쪽 subtree, 오른쪽은 오른쪽 subtree로 나눌 수 있다.

 

pre-order를 출력하기 위해서는 트리의 루트를 알아야 한다. 그리고 두 subtree에 대해서 재귀 함수를 호출하면 된다.

 

이때 post-order의 마지막을 알아내는 것은 쉽지만 in-order에서도 루트를 찾아야 한다. 일단 무지성으로 in-order에서 선형 탐색을 통해 루트가 몇 번째 인덱스에서 등장하는지를 찾았다. 그 인덱스를 사용해서 현재 subtree를 왼쪽, 오른쪽 subtree로 나눈다. 그리고 post-order도 나눠줘야 한다. in-order의 시작 인덱스와 루트 인덱스의 차이를 이용하면 왼쪽 subtree의 크기를 구할 수 있다. 이는 post-order에서도 동일한 크기를 가지기 때문에 post-order에서도 subtree를 분할할 수 있다.

 

이때 선형 탐색을 사용하는 경우엔 시간이 많이 걸릴 수 있다. 생각했을 때 최악의 경우 O(N^2) 정도 걸리지 않을까 싶다. 균형 이진트리라서 분할이 적게 되는 경우엔 괜찮지만 편향 이진트리면 꽤나 시간을 잡아먹을 것 같다. 이 점을 극복하기 위해 in-order에서의 인덱스를 저장하는 배열을 추가로 만든다. 그러면 in-order에서의 루트 인덱스를 O(1)에 구할 수 있게 된다. 실제로 1220ms에서 28ms로 시간이 파격적으로 줄었다.

 

그런데 메모리도 선형 탐색을 하는 쪽이 더 높게 나왔다. 아무래도 배열이 하나 없기 때문에 메모리라도 적게 나와야 하지 않나 싶었는데 왜 더 높게 나왔는지 모르겠다. for문에서 매번 int 변수 하나를 쓰는 게 문젠가 싶어서 int를 전역으로 바꿨더니 메모리가 더 크게 나왔다. 뭐지...? 테스트 케이스를 정확히 알 수 없기 때문에 못 알아낼 것 같다.

 

idx 배열의 크기를 100000으로 사용했더니 출력 초과가 나왔었다. 그 이유는 입력이 1부터 n까지 들어오기 때문에 인덱스가 100000까지 필요하기 때문에 out of bound가 나왔던 것이었다. 디테일을 놓쳤다.

 

 

후기)

오랜만에 본 트리 순회 삼형제였다.