[프로그래머스 > LV2] 요격 시스템(Kotlin)

프로그래머스

 

1. 문제

[입력]

각 폭격 미사일의 x좌표 범위 목록 targets

🌹 targets는 (s,e) 형태이며, 해당 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다.

[결과]

모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return

 

2. 풀이

먼저 미사일들을 구간을 기준으로 오름차순 정렬할 필요가 있습니다. 🤗

targets.sortWith(compareBy({ it[0] }, { it[1] }))

 

그럼 필요한 요격 미사일의 최소 개수를 구할 수 있을까요?

중복되는 구간을 적절히 이용할 필요가 있습니다.

• 초기 구간은 (s1, e1)입니다.
• target 2의 s가 구간 e1보다 작으니, 아직까지는 요격 미사일을 쏘지 않습니다.
• 이 때의 구간은 target 1과 target 2가 겹치는 (s2, e1) 입니다.
• target 3의 s가 구간 e1보다 작으니, 아직까지는 요격 미사일을 쏘지 않습니다.
• 이 때의 구간은 (s2, e1)과 (s3, e3)가 겹치는 (s3, e3) 입니다.
• target 4의 s가 구간 e3보다 크기, 구간이 겹치지 않습니다. 그렇다면 이전 구간에 속해있는 미사일을 요격해 제거해줄 필요가 있습니다. 요격 미사일 1개가 필요하게 됩니다.
• 마지막 target4 미사일이 남아있으므로 이를 요격해줄 필요가 있습니다. 결과 요격 미사일은 총 2개가 필요합니다.

위에 서술한 프로세스를 코드로 구현하면 아래오 같습니다.

3. 코드

Kotlin

import kotlin.math.min
class Solution {
    fun solution(targets: Array<IntArray>): Int {
        /**
         *   현재 구간을 (s, e)라 할 때, i번째 미사일의 si가 구간 내에 있을 때는 구간을 (si, min(ei, e))로 변경
         *   그러지 않을 경우 answer + 1, 구간을 (si, ei)로 갱신
         **/
        var answer: Int = 0
        targets.sortWith(compareBy({ it[0] }, { it[1] }))
        var (s, e) = targets.first() // 첫 구간
        (1 until targets.size).forEach {
            val (si, ei) = targets[it]
            e = if (si < e) { // si가 구간 내에 있을 때
                min(ei, e)
            } else {
                answer++
                ei
            }
            s = si
        }
        // 마지막에 요격하지 못한 미사일들을 한번에 처리하도록 + 1
        return answer + 1
    }
}