코틀린 코딩테스트 강좌, 최소 공통 조상 구하기 1

예제 입력

7
1 2 3
2 4 5
3 6 7
4 -1 -1
5 -1 -1
6 -1 -1
7 -1 -1
4 5

예제 출력

2

문제 풀이 과정

문제를 해결하기 위해서는 다음과 같은 과정을 거쳐야 합니다:

1단계: 이진 트리 구성

먼저, 입력을 받아 이진 트리를 구성해야 합니다. 트리는 각 노드가 부모, 왼쪽 자식, 오른쪽 자식을 가지도록 구성될 것입니다. 이를 위해, 노드 클래스(Node)를 정의하고, 트리 구조를 저장할 수 있는 방식으로 구현합니다.

data class Node(val value: Int) {
    var left: Node? = null
    var right: Node? = null
}

2단계: 부모 트리 구성

트리를 구성할 때 각 노드의 부모를 추적할 수 있는 구조도 필요합니다. 따라서, 부모 노드를 모두 기록하여 어떤 노드가 부모인지 쉽게 찾을 수 있는 구조를 만듭니다.

val parentMap = mutableMapOf()

3단계: 두 노드의 경로 찾기

두 노드 A와 B의 경로를 찾아야 합니다. 이는 두 노드의 조상을 모아 각 노드가 각각의 경로를 따르게 만들어, 후에 최소 공통 조상을 찾는 데 유용합니다. 이를 위해 A와 B의 부모를 추적하며 경로를 저장합니다.

fun findPathToRoot(node: Int): List {
    val path = mutableListOf()
    var current = node
    while (current != -1) {
        path.add(current)
        current = parentMap[current] ?: -1
    }
    return path
}

4단계: 최소 공통 조상 찾기

A와 B 각각의 경로를 구한 후, 두 경로를 비교하여 가장 마지막에 만나는 조상을 찾습니다. 경로를 거꾸로 비교해서 최소 공통 조상을 찾으면 됩니다.

fun findLCA(nodeA: Int, nodeB: Int): Int {
    val pathA = findPathToRoot(nodeA)
    val pathB = findPathToRoot(nodeB)
    
    var lca = -1
    for (i in 0 until minOf(pathA.size, pathB.size)) {
        if (pathA[pathA.size - 1 - i] == pathB[pathB.size - 1 - i]) {
            lca = pathA[pathA.size - 1 - i]
        } else {
            break
        }
    }
    return lca
}

5단계: 전체 알고리즘 조합

위의 모든 단계를 조합하여 입력을 받아 실행하는 메인 함수를 작성합니다.

fun main() {
    val n = readLine()!!.toInt()
    for (i in 0 until n) {
        val (parent, left, right) = readLine()!!.split(" ").map { it.toInt() }
        if (parent != -1) {
            parentMap[parent] = parent
            if (left != -1) parentMap[left] = parent
            if (right != -1) parentMap[right] = parent
        }
    }
    val (a, b) = readLine()!!.split(" ").map { it.toInt() }
    
    val lca = findLCA(a, b)
    println(lca)
}

복잡도 분석

본 알고리즘의 시간 복잡도는 O(N)입니다. 이는 모든 노드를 한 번씩 방문하기 때문입니다. 공간 복잡도 또한 O(N)으로, 부모 관계를 저장하는 데 사용되는 공간 때문입니다. 이 알고리즘은 주어진 문제를 효율적으로 해결할 수 있습니다.

결론

이번 강좌에서는 이진 트리에서 최소 공통 조상을 찾는 방법에 대해 알아보았습니다. 이 알고리즘을 통해 트리 구조에 대한 이해도를 높일 수 있으며, 다양한 문제를 해결하는 데 도움을 줄 것입니다. 다음 강좌에서는 다른 유형의 트리 문제를 다룰 계획입니다. 감사합니다!