문제링크

Goal

• Get preOrder from inOrder and postOrder

Solution

• postOrder의 마지막 index는 항상 root 입니다.
• inOrder는 root를 기준으로 왼쪽은 root의 left child, 오른쪽은 right child 입니다.
• postOrder에서 root를 구하고 inOrder에서 root의 index를 구한 뒤 index를 통해 left child 개수(numberOfLeftNode)를 구합니다.
• inOrder의 경우 (start ~ rootIndex - 1)가 left child node이고, (rootIndex + 1 ~ end)가 right child node 입니다.
• postOrder의 경우 (start ~ start + numberOfLeftNode - 1)가 left child node 이고, (start + numberOfLeftNode ~ end - 1)가 right child node 입니다.
• 위 과정을 재귀적으로 구현합니다.

풀이 1

• postOrder에서 구한 root를 inOrder의 index로 구하는 과정을 Linear Search로 구현하였습니다.

import java.io.BufferedReader
import java.io.BufferedWriter

fun main() {
    val bufferedReader = System.`in`.bufferedReader()
    val bufferedWriter = System.out.bufferedWriter()

    val n = bufferedReader.readLine().toInt()
    val inOrder = getOrder(bufferedReader)
    val postOrder = getOrder(bufferedReader)

    printPreOrder(bufferedWriter, inOrder, postOrder, 0, n - 1, 0, n - 1)

    bufferedReader.close()
    bufferedWriter.close()
}

fun getRootIndexFromInOrder(inOrder: List<Int>, root: Int): Int {
    for (i in inOrder.indices) {
        if (inOrder[i] == root) return i
    }
    return -1
}

fun printPreOrder(
    bufferedWriter: BufferedWriter,
    inOrder: List<Int>,
    postOrder: List<Int>,
    inStart: Int,
    inEnd: Int,
    postStart: Int,
    postEnd: Int
) {
    if (inStart > inEnd || postStart > postEnd) return

    val rootIndexFromInOrder = getRootIndexFromInOrder(inOrder, postOrder[postEnd])
    bufferedWriter.write("${inOrder[rootIndexFromInOrder]} ")
    val numberOfLeftNode = rootIndexFromInOrder - inStart

    printPreOrder(
        bufferedWriter,
        inOrder,
        postOrder,
        inStart,
        rootIndexFromInOrder - 1,
        postStart,
        postStart + numberOfLeftNode - 1
    )
    printPreOrder(
        bufferedWriter,
        inOrder,
        postOrder,
        rootIndexFromInOrder + 1,
        inEnd,
        postStart + numberOfLeftNode,
        postEnd - 1
    )
}

fun getOrder(bufferedReader: BufferedReader): List<Int> {
    return bufferedReader
        .readLine()
        .split(" ")
        .map { it.toInt() }
}

풀이 2

• postOrder에서 구한 root를 사전에 정의한 inOrderMap을 통해 바로 index를 구할 수 있도록 구현하였습니다.

import java.io.BufferedReader
import java.io.BufferedWriter

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter
private lateinit var inOrder: List<Int>
private lateinit var postOrder: List<Int>
private lateinit var inOrderMap: MutableMap<Int, Int>

fun main() {
    bufferedReader = System.`in`.bufferedReader()
    bufferedWriter = System.out.bufferedWriter()

    val n = bufferedReader.readLine().toInt()
    inOrder = getOrder()
    postOrder = getOrder()

    inOrderMap = mutableMapOf()
    inOrder.forEachIndexed { index, node ->
        inOrderMap[node] = index
    }

    printPreOrder(0, n - 1, 0, n - 1)

    bufferedReader.close()
    bufferedWriter.close()
}

fun printPreOrder(inStart: Int, inEnd: Int, postStart: Int, postEnd: Int) {
    if (inStart > inEnd || postStart > postEnd) return

    val rootIndexFromInOrder = inOrderMap[postOrder[postEnd]]!!
    bufferedWriter.write("${inOrder[rootIndexFromInOrder]} ")
    val numberOfLeftNode = rootIndexFromInOrder - inStart

    printPreOrder(inStart, rootIndexFromInOrder - 1, postStart, postStart + numberOfLeftNode - 1)
    printPreOrder(rootIndexFromInOrder + 1, inEnd, postStart + numberOfLeftNode, postEnd - 1)
}

fun getOrder(): List<Int> {
    return bufferedReader
        .readLine()
        .split(" ")
        .map { it.toInt() }
}

주석 없는 코드를 만들기 위해 노력하는 개발자입니다.

혹시라도 의도가 분명하지 않아보이는 (이해가 되지 않는) 코드가 있으시다면 편하게 답변 달아주시면 정말 감사하겠습니다.