후기

처음 떠올린 풀이

처음에는 각 미사일 구간을 서로 비교하면서, 겹치는 미사일들을 하나의 요격 미사일로 처리하려고 하였습니다.

예를 들어 다음과 같이 구간이 겹치면 한 번에 요격할 수 있다고 생각하였습니다.

(1, 4)
  (2, 5)

이러한 구간을 찾기 위해 이중 반복문을 사용하고, 이미 확인한 구간은 cur로 건너뛰는 방식을 시도하였습니다.

for (let i = 0; i < targets.length; i++) {
    for (let j = i + 1; j < targets.length; j++) {
        // targets[i]와 targets[j] 비교
    }
}

하지만 문제를 풀다 보니 cur가 정확히 어떤 구간까지 처리했다는 뜻인지 불분명해졌고, 겹치는 구간을 발견했을 때와 겹치지 않는 구간을 발견했을 때 answer를 언제 증가시켜야 하는지도 복잡해졌습니다.

구간의 끝점을 기준으로 정렬

이 문제의 핵심은 미사일을 시작점이 아니라 끝점이 작은 순서대로 정렬하는 것이었습니다.

targets.sort((a, b) => a[1] - b[1]);

가장 먼저 끝나는 미사일을 놓치지 않으려면 그 미사일의 끝점 바로 직전에 요격 미사일을 발사해야 합니다.

예를 들어 첫 번째 미사일이 (1, 4)라면 실제 요격 위치는 다음과 같이 생각할 수 있습니다.

(1────────4)
           ↑
       4 바로 직전

정확히 4에서 발사할 수는 없습니다. 미사일 구간이 (s, e) 형태의 개구간이기 때문입니다.

따라서 실제 소수 위치를 저장하는 대신 lastEnd = 4를 저장하고, 이후 미사일의 시작점이 4보다 작은지만 확인하면 됩니다.

조건문의 의미를 반대로 이해한 부분

작성한 코드에서는 다음과 같이 조건을 사용하였습니다.