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

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

제한사항

1 ≤ targets의 길이 ≤ 500,000
targets의 각 행은 [s,e] 형태입니다.이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야 합니다.
0 ≤ s < e ≤ 100,000,000

 

제한사항을 보았을 때 수가 상당히 큰 것을 볼 수 있음. 그래서 여러 알고리즘을 제거할 수 있었음

 

다만, 어떤 알고리즘도 활용 방법에 대해 떠오르지 않았음. 여러 아이디어들이 떠올랐지만 그 방식이 최적이 되는지가 판단이 되지 않았음

 

범위를 오름차순으로 정렬하여 문제를 풀이할 수 있을 것이라 생각했고 처음에는 start 기준으로 오름차순 정렬하여 문제를 해결하려 했음

 

start 기준으로 했을 때 범위 내에 들어오는지 확인하기 위해 추가적인 로직이 필요함

 

따라서 end 기준으로 오름차순 정렬하여 다음 start가 범위 내에 있는지 확인하고 범위 밖이라면 end 기준을 업데이트하도록 구현

 

문제의 원리를 빨리 파악하고 이해하여 적절한 풀이 방식을 떠올리는 게 필요함

function solution(targets) {
    var answer = 0;
    
    const sorted = targets.slice().sort((a,b) => a[1] - b[1])
        
    let rangeEnd = sorted[0][1];
    answer++;
    
    for(let i = 0; i < sorted.length; i++){
        const [start, end] = sorted[i];
        if(start < rangeEnd){
            continue;
        } else {
            rangeEnd = end;
            answer++;
        }
    }
    
    return answer;
}