요격 시스템 - kotlin

A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다.
A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다.
A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다.
각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

풀이 과정

처음엔 가장 많이 나온 지점을 요격하고 그 구간에 해당하는 미사일들을 삭제해서 그 개수를 세려했다. 하지만 문제 조건에 끝 지점에는 피격 판정을 두지 않았고, 그래서 요격 구간에 미사일이 존재하면 범위를 좁혀주고 존재하지 않으면 요격 구간을 추가해주기로 했다.

fun solution(targets: Array<IntArray>): Int {
    val counters = mutableListOf<IntRange>()
    targets.sortBy { it.first() }

    B@ for (i in targets.indices) {
        val range = targets[i].first() until targets[i].last()
        for (j in counters.indices) {
            if (counters[j].intersect(range).isNotEmpty()) {
                val start = Math.max(counters[j].first, range.first)
                counters[j] =
                    start .. Math.min(counters[j].last, Math.max(start, range.last))
                continue@B
            }
        }
        counters.add(range)
    }

    return counters.count()
}

정확성만 신경썼기에 효율성에서 시간초과와 메모리 초과가 있었고, 효율성을 개선해보기로 했다.

1차 개선 (효율성)

문제 해결을 위해 고민하던 중 범위들의 끝 값을 기준으로 정렬하고 범위 안에 있으면 끝점 갱신, 없으면 answer에 1을 더하고 다시 반복해주는 방법의 힌트를 얻었다.

fun solution(targets: Array<IntArray>): Int {
    var end = 0
    var answer = 0

    targets.sortWith(compareBy { it.last() })

    for (i in targets.indices) {
        val startCurrent = targets[i].first()
        val endCurrent = targets[i].last()

        if (startCurrent < end) continue
        else {
            end = endCurrent
            answer++
        }
    }

    return answer
}

해당 코드를 통해 간결하고 효율성있게 해결할 수 있었다.