[Kotlin] 백준 10775 공항

📘 문제

https://www.acmicpc.net/problem/10775

💡 풀이

접근방식

i번째 비행기가 주어진 값을 통해 게이트에 도킹할 수 있는지 여부를 체크하기 위해서는
주어진 값부터 체크하며 1번 게이트까지 탐색을 해야한다고 생각했다.
왜냐하면 문제에서 요구하는 output은 최대 값이기 때문에, 도킹할 수 있는 게이트 중 내림차순으로 들어가야 최대로 들어갈 수 있기 때문이다.
예를 들면 1번째 비행기의 값이 4가 주어지고 2번째 비행기의 값이 1로 input일 때
1번째 비행기가 1번 게이트부터 들어간다고 하면 2번째 비행기는 도킹할 수 없어 그대로 1대의 비행기만 도킹이 가능하다. 하지만, 1번째 비행기가 input대로 4번 게이트부터 도킹한다면 2번째 비행기는 1~3번 게이트라는 선택권이 주어지고 도킹 가능한 비행기는 전자보다 많은 2대의 비행기가 된다.

이를 효율적으로 구현하기 위해서는 많은 방법들이 있겠지만, 나는 그리디+union-find 알고리즘을 선택했다.
코드는 단순하기에 union-find 알고리즘을 공부하고 위의 있는 접근방식을 본다면 코드를 보고 이해가 될 것이다.

코드

private lateinit var gates: IntArray
private fun main() {
    gates = IntArray(readln().toInt() + 1) { it }
    var answer = 0
    for (i in 1..readln().toInt()) {
        val ableDockGate = find(readln().toInt())
        if (ableDockGate == 0) break
        answer = i
        union(ableDockGate, ableDockGate - 1)
    }
    println(answer)
}

private fun find(x: Int): Int {
    if (x == gates[x]) return x
    gates[x] = find(gates[x])
    return gates[x]
}

private fun union(x: Int, y: Int) {
    val findX = find(x)
    val findY = find(y)
    if (findX == findY) return
    gates[findX] = findY
}

결과