[Javascript] 프로그래머스 - 요격 시스템

문제 설명

A 나라가 B 나라를 침공하며, B 나라의 전략 자원 보호를 위해 최소한의 요격 미사일을 사용하여 모든 폭격 미사일을 요격해야 합니다.
각 폭격 미사일은 (s, e)의 개구간으로 표현되며, 특정 x 좌표에서 y 축에 수평이 되도록 요격 미사일을 발사하면 해당 x 좌표에 걸쳐 있는 모든 폭격 미사일을 요격할 수 있습니다.
최소한의 요격 미사일 수를 구하는 문제입니다.

---

제한 사항

• 1 ≤ targets.length ≤ 500,000
• 0 ≤ s < e ≤ 100,000,000
• (s, e) 형태의 개구간으로 표현된 폭격 미사일은 s와 e에서 요격할 수 없음.
• 요격 미사일은 실수 x 좌표에서도 발사 가능.

---

해결 방법

알고리즘: 그리디(Greedy) 기법

1. 폭격 미사일을 끝 지점 기준으로 오름차순 정렬합니다.
2. 가장 먼저 끝나는 미사일의 종료 지점에 요격 미사일을 배치합니다.
3. 이후 요격 미사일로 커버되지 않는 다음 미사일을 찾아 반복합니다.
4. 이를 통해 최소한의 요격 미사일 수를 구할 수 있습니다.

---

시간 복잡도

• 정렬: O(N log N)
• 탐색 및 갱신: O(N)
• 총 시간 복잡도: O(N log N) (최대 50만 개 데이터 처리 가능)

---

구현 코드

function solution(targets) {
    let answer = 0;
    
    targets.sort((a, b) => a[1] - b[1]);

    let curNum = -1;
    for (const [a, b] of targets) {
        if (a >= curNum) {
            curNum = b;
            ++answer;
        }
    }
    
    return answer;
}