[프로그래머스] 요격 시스템

사용 언어: Kotlin

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

요격을 하면 수직선상의 모든 미사일을 한번에 요격할 수 있다.

정수 쌍(s, e)으로 이루어진 길이의 미사일들을 모두 요격하려고 할 때, 최소한으로 필요한 요격 횟수를 return한다.

제한사항

target(s,e) = s부터 e까지의 길이를 가진 미사일

0 <= s < e <= 100,000,000

targets = target(s,e)의 배열

1 <= targets의 길이 <= 500,000

풀이

답이 될 수 있는 최대값은 targets의 길이와 같다.

최소값을 구하기 위해서, 가장 중요한 포인트는 두 미사일의 범위가 겹치는 곳을 요격하면, 한번에 처리할 수 있는 것이다.

 

targets를 e를 기준으로 오름차순 정렬한 후에

가장 e가 작은 미사일의 e좌표로 요격을 하며,

s좌표를 기준으로 검사하여 겹치는 미사일을 제거해주면 된다. 이때, 겹치지 않는 미사일이 나오면, 이후는 순회할 필요가 없다. (이후에 겹치는 미사일이 있더라도)

 

(1,3), (2,5), (4,6), (1,7)

 

위와 같이 미사일이 있다고 하면, 3좌표로 요격을 했을 때 (1,3), (2,5)만 제거해주더라도 (4,6) 미사일에 의해 좌표 6을 요격했을 때, (1,7) 미사일도 제거된다.

 

 

 

코드

fun solution(targets: Array<IntArray>): Int {
    val queue = ArrayDeque<IntArray>(0)
    targets.sortedBy { it[1] }.forEach { queue.add(it) }
    var result = 0
    while(queue.isNotEmpty()) {
        val targetIndex = queue.removeFirst()
        while(queue.isNotEmpty() && targetIndex[1] > queue.first()[0]) {
            queue.removeFirst()
        }
        result++
    }
    return result
}