(프로그래머스 | Kotlin) - 요격 시스템

해결 방법

문제를 해석하면 특정 구간이 여러 개 주어지고 그 구간들을 전부 관통할 수 있는 최소의 폭격 미사일 수를 구해야 한다. 문제에서 그리디 알고리즘 문제를 좀 풀어봤다면 예시로 던져준 사진을 보자마자 그리디 문제임을 알아챘을 것이다. 따라서 이 문제는 그리디 알고리즘을 이용해서 해결하면 된다. 해결 순서는 다음과 같다.

1. targets 내 특정 구간 i 에 대해서 targets[i][1] 을 기준으로 정렬한다.

2. 첫 폭격 미사일 설치 위치를 targets[0][1] 로 설정한다.

   var lastSpot = targets[0][1]
   

3. 반복문을 통해 정렬된 targets 내의 모든 원소들을 차례로 돌면서 현재 원소의 시작 위치가 lastSpot 위치보다 같거나 크다면 해당 원소의 끝 위치가 다음 폭격 미사일의 설치 위치가 된다.

   for(i in targets.indices) {
       if(targets[i][0] >= lastSpot) {
           lastSpot = targets[i][1]
           answer++
       }
   }
   

4. 3번 반복문 내의 조건문이 충족될 때마다 answer (설치해야 할 폭격 미사일 갯수) 를 증가시킨다.

설명

순서 1.

모든 원소는 시작과 끝 값을 가지고 있다. 여기서 끝 값을 기준으로 오름차순 정렬을 해주면 특정 원소 인덱스 i 다음부터 모든 원소들의 끝 값은 i 번째 원소의 끝 값보다 무조건 같거나 크다. 그래서 i+1 부터 끝 원소까지 차례로 탐색하면서 시작 위치 값이 i 위치의 끝 값보다 같거나 큰 원소가 나오면 해당 원소의 끝에 폭격 미사일을 설치하면 된다.

순서 2.

끝 좌표 기준으로 정렬된 상태라면 폭격 미사일을 특정 원소의 끝 좌표를 겨냥해서 설치하는 것이 최대한 많은 원소들을 관통할 확률을 높여준다. 문제 예시 사진처럼 직접 정렬된 형태로 그려놓고 시작 위치에 폭격 미사일을 설치하는 것과 끝 위치에 폭격 미사일 설치하는 것을 비교하면 무슨 말인지 이해할 수 있다.

순서 3.

문제 조건에서 조심해야 할 점은 시작, 혹은 끝 위치는 폭격이 불가능하다는 것이다. 그래서 특정 원소 i 의 끝 위치가 , i+1 의 시작 위치와 같다고 해도 i 끝 위치에 설치해서 하나로 두 개를 터트릴 수 없다는 뜻이다.

그래서 2번에 설명한 끝 위치라는 것은 실제로 끝 값을 의미하는 것이 아닌 최대한 끝 값에 가까운 값으로 가정해서 코드를 작성한다. 배열은 끝 값이 저장되지만 머릿속으로는 끝 값에 가까운 값이라고 생각하면서 문제를 풀면 된다. 이런 이유로 반복문 내 조건문은 현재 원소의 시작 위치가 마지막으로 설치된 폭격 미사일 위치와 같아도 미사일을 새로 설치해야 한다.

전체 코드

class Solution {
    fun solution(targets: Array<IntArray>): Int {
        targets.sortBy {it[1]}
        var answer= 1
        var lastSpot = targets[0][1]

        for(i in targets.indices) {
            if(targets[i][0] >= lastSpot) {
                lastSpot = targets[i][1]
                answer++
            }
        }
        return answer
    }
}