문제 링크

문제 풀이 아이디어

시간복잡도

0 ≤ s < e ≤ 100,000,000의 조건을 보면 절대로 수직선 위에 미사일을 표시한다거나 해서 N을 100,000,000만들어서 풀면 안됩니다. 이렇게 하면 O(N)만 해도 시간초과가 바로 날 것입니다. 따라서 s, e는 순환해서는 안되고 서로 값을 비교만 해야 합니다. 이런 조건은 문제를 푸는데 장애물이기도 하지만 일종의 힌트이기도 합니다. 무조건 targets의 길이만 반복문에 사용할 수 있다는 것이죠.

targets의 길이는 500,000입니다. 역시 O(N^2)의 시간복잡도를 가지는 풀이는 곤란합니다. 저는 정렬과 그리디로 이 문제를 풀었는데요. 시간복잡도는 O(NlogN) + O(N) = O(NlogN)입니다.

정렬 + 그리디

위의 시간복잡도 조건에서 볼 수 있듯이 우리는 targets를 단 1번만 순회해야 합니다. 따라서 targets를 일정 조건에 따라서 정렬한 뒤 그리디를 활용해서 풀도록 하겠습니다.

일단 targets를 끝점, 즉 target[1]를 기준으로 내림차순으로 정렬하겠습니다. 끝점이 같은 경우는 시작점(target[0])를 기준으로 내림차순으로 정렬합니다.

이렇게 정렬하고 앞에서 부터 미사일이 겹치는지 안 겹치는지 확인하면서 그리디를 실행합니다. 최대한 많은 미사일을 맞추기 위해서 현재 격추할 미사일 끝점 직전에 (경계선에 쏘면 안된다고 했으므로) 요격 미사일을 쏜다고 합시다. 이 때 뒤에 있는 미사일들이 이 요격 미사일에 격추되는지 확인합니다. 만약 격추되지 않는다면 그 미사일부터 다시 그 미사일의 끝점 직전에 쏜다고 하고 다음 미사일들을 확인해나가면 됩니다.

끝점을 기준으로 정렬한 이유

정렬된 폭격 미사일을 최대한 효율적으로 요격하는 방법은 최대한 뒤쪽에 쏴야합니다. 시작점을 기준으로 정렬하게 된다면 시작점은 빠르지만 끝점이 뒤에 있는 긴 미사일이 있는 경우 중간의 범위에 들어가는 미사일들이 무시될 수 있습니다. 아래 예시처럼 말이죠.

// 미사일 1   -------------------------------------------------------------
// 미사일 2         ---------
// 미사일 3              ---------

그렇다면 겹치는 부분을 계산하면 되는 것이 아니냐고 생각할 수 있습니다. 하지만 그렇게 하면 훨씬 복잡합니다. 미사일 1, 2가 겹치고 2, 3이 겹친다고 반드시 1, 3이 겹친다고 할 수 없습니다.

// 미사일 1 ----------
// 미사일 2      ------------
// 미사일 3                -------

따라서 그리디를 적용하기 위해서는 위처럼 끝점의 순서대로 정렬하고 최대한 끝에 발사한다고 가정하는 방법이 최선입니다.

코드

func solution(_ targets:[[Int]]) -> Int {

    // 정렬: 끝점을 기준으로 내림차순, (같으면 시작점)
    let targets = targets.sorted { t1, t2 in
        if t1[1] == t2[1] {
            return t1[0] < t2[0]
        } else {
            return t1[1] < t2[1]
        }
    }

    // 현재 요격 미사일 갯수
    var ans = 0
    // 현재 요격 미사일을 쏘는 위치
    var nowEnd = 0
    
    // 폭격 미사일이 겹치는 조건: 시작점 < 끝점
    for target in targets {
        if target[0] >= nowEnd {
            ans += 1
            nowEnd = target[1]
        }
    }

    return ans
}