백준 11509번: 풍선 맞추기 (Kotlin)

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

11509번: 풍선 맞추기

안녕하세요, 이륙사입니다. 이번 게시물에서는 풍선 맞추기 문제의 풀이 과정을 복기하며 기록했습니다. 백준에서 그리디 알고리즘이라고 나와있지만, 개인적으로는 어떻게 단일 반복문으로 해결할 수 있을까에 대한 구현 문제에 가깝다고 느꼈습니다.

 

풀이 과정

먼저, 최소한의 화살을 사용하기 위해선 하나의 화살로 최대한 많은 풍선을 터뜨려야 합니다.

화살은 풍선을 하나 맞힐 때마다 높이가 1씩 감소하므로, 내림차순으로 높이가 1 차이나는 풍선들은 높이가 가장 큰 풍선에 화살을 한번 쏘는 것으로 그 풍선들을 모두 맞힐 수 있습니다. 

 

위의 예시의 경우, 3개의 화살(화살1(5, 4, 3), 화살2(5, 4, 3), 화살3(2, 1))로 풍선들을 전부 맞힐 수 있습니다.

 

접근

저는 먼저 이중 반복문으로 완전 탐색하는 방법을 떠올렸습니다. 앞에 있는 풍선에 화살을 쏘고, 뒤에 그 화살로 제거할 수 있는 풍선들이 있는지 확인하는 것입니다. 그럴려면 이중 반복문을 사용해야 하는데, 풍선이 최대 100만개라서 이 방법으론 시간 내에 해결이 불가능했습니다.

 

단일 반복문으로 줄일 수 있을까 고민하다가, 이중 반복문을 사용해도 날아가는 화살의 높이를 알고 있어야 한다는 점에 주목했습니다. 반복문으로 풍선들을 확인할 때 이때까지 쏜 화살 중 현재 확인하는 풍선의 높이로 날아오고 있는 화살이 있으면 쏘지 않고(저장x), 없으면 새로 쏘면 되겠다. 즉, 해싱(or 인덱스: 풍선 높이, 원소: 화살 개수)을 사용하면 단일 반복문으로 해결할 수 있겠다고 생각했습니다. 

 

val arrows = IntArray(MAX_HEIGHT + 1) // 날아가고 있는 화살을 높이에 따라 저장

balloons.forEach { height ->
    if (arrows[height] == 0) {  // height 높이에 날아오는 화살이 없으면
        count += 1              // 쏜다
        arrows[height - 1] += 1 // 풍선에 맞고 화살 높이 감소
    } else if (arrows[height] > 0) { // 날아오는 화살이 있으면
        arrows[height] -= 1          // 풍선에 맞는다
        arrows[height - 1] += 1
    }
}

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

const val MAX_HEIGHT = 1_000_000

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())
    val balloons = IntArray(n) {
        st.nextToken().toInt()
    }
    var count = 0
    val arrows = IntArray(MAX_HEIGHT + 1) // 날아가고 있는 화살을 높이에 따라 저장

    balloons.forEach { height ->
        if (arrows[height] == 0) {  // height 높이에 날아오는 화살이 없으면
            count += 1              // 쏜다
        } else if (arrows[height] > 0) { // 날아오는 화살이 있으면
            arrows[height] -= 1          // 풍선에 맞는다
        }

        arrows[height - 1] += 1 // 풍선에 맞고 화살 높이 감소
    }

    print(count)
}