[백준 - 11509] 풍선 맞추기

문제 링크

첫번째 시도 (시간 초과)

• 제출번호: 39431031
• 가장 간단한 방법인 이중 반복문으로 구현했지만 당연히 시간 초과가 발생했습니다.

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

    val n = bufferedReader.readLine().toInt()
    val h = bufferedReader.readLine().split(" ").map { it.toInt() }
    val popped = Array(n) { false }

    var answer =0
    for (i in 0 until n) {
        var arrow = h[i]
        if (!popped[i]) {
            popped[i] = true
            arrow--
            for (j in i + 1 until n) {
                if (!popped[j] && arrow == h[j]) {
                    popped[j] = true
                    arrow--
                }
            }
            answer++
        }
    }
    bufferedWriter.write("$answer")

    bufferedReader.close()
    bufferedWriter.close()
}

두번째 시도 (성공)

• 제출번호: 39431375
• 여전히 최악의 시간 복잡도는 O(N^2)이기 때문에 시간 초과가 날 것이라고 예상했지만, 가까스로 성공했다고 생각합니다.

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

    val n = bufferedReader.readLine().toInt()
    val h = bufferedReader.readLine().split(" ").map { it.toInt() }
    val arrows = mutableListOf<Int>()

    var answer = 0
    for (i in 0 until n) {
        if (arrows.contains(h[i] + 1)) {
            arrows.remove(h[i] + 1)
        } else answer++
        arrows.add(h[i])
    }
    bufferedWriter.write("$answer")

    bufferedReader.close()
    bufferedWriter.close()
}

세번째 시도 (성공)

• 제출번호: 39431709
• O(N)의 시간복잡도를 가집니다.
• 모든 높이에 해당하는 화살에 대한 메모리를 할당함으로써 풍선이 위치한 높이를 Key로 가지고 해당 높이에 존재하는 화살의 개수를 Value를 가지는 Key-Value 쌍으로 문제를 해결할 수 있었습니다.

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

    val n = bufferedReader.readLine().toInt()
    val h = bufferedReader.readLine().split(" ").map { it.toInt() }
    val arrows = Array(1_000_001) { 0 }

    var answer = 0
    for (i in 0 until n) {
        if (arrows[h[i]] == 0) answer++
        else arrows[h[i]]--
        arrows[h[i] - 1]++
    }
    bufferedWriter.write("$answer")

    bufferedReader.close()
    bufferedWriter.close()
}

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

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