백준 2263 트리의 순회 Kotlin (트리)

문제 출처 : https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

문제

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

입력

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

출력

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

알고리즘 분류

• 트리
• 분할 정복
• 재귀

풀이

트리 순회의 특징에 관한 문제이다.

중위 순회와 후위 순회의 결과가 주어지고, 이를 이용해 전위 순회한 결과 값을 출력해야 한다.

전위 순회 : VLR

중위 순회 : LVR

후위 순회 : LRV

후위 순회는 가장 마지막 값이 루트 노드인 것을 이용하면 중위 순회의 결과값에서 루트 노드가 몇 번째 인덱스로 나타나는지 알 수 있다.

후위 순회와 중위 순회의 결과가 각각

6 8 7 1 4 5 3 2 //후위 순회

6 1 7 8 2 4 3 5 //중위 순회

이라고 하면,

후위 순회의 가장 마지막 값인 2가 루트 노드이므로 중위 순회의 값에 다음과 같이 표현할 수 있다.

6 1 7 8 2 4 3 5 

전위 순회는 루트 노드가 맨 앞에 와야 한다.

따라서 위의 중위 순회 결과값을 루트 노드 기준으로 재귀적으로 왼쪽 구역, 오른쪽 구역 나누어서 루트 값을 찾아가면 된다.

이때 후위 순회 결과값에서 루트를 찾아야 하므로, 위에서 왼쪽, 오른쪽 구역을 나눌 때 후위 순회의 범위도 다시 설정해 주어야 한다.

 

재귀 함수 내부는, 전위 순회이므로 루트를 먼저 출력한 후 왼쪽, 오른쪽 루트를 찾는 재귀 함수를 호출한다.

인덱스 배열은 따로 정의해 놓고 사용하자.

 

코드

val br = System.`in`.bufferedReader()
val bw = System.out.bufferedWriter()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
lateinit var inOrder: List<Int>
lateinit var inIndex: IntArray
lateinit var postOrder: List<Int>
fun getRoot(start: Int, end: Int, postStart: Int,  postEnd: Int){
    if(postStart>postEnd) return
    var rootIdx = inIndex[postOrder[postEnd]]
    val leftSize = rootIdx - start
    bw.write("${inOrder[rootIdx]} ")
    //왼쪽
    getRoot(start, rootIdx-1, postStart, postStart + leftSize-1)
    //오른쪽
    getRoot(rootIdx+1, end, postStart+leftSize, postEnd-1)
}

fun main(){
    //input
    val n = getInt()
    inOrder = getIntList()
    postOrder = getIntList()
    inIndex = IntArray((n+1))
    for(i in inOrder.indices){
        inIndex[inOrder[i]] = i
    }
    //solve
    getRoot(0,n-1,0,n-1)

    bw.close()
}