프로그래머스 요격 시스템

문제

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

---

문제 설명

A 나라와 B 나라 간에 전쟁중에 A는 x축에 평행한 미사일을 발사하고, B 나라는 이를 수직으로 요격한다. 조건은 미사일의 양 끝에서는 요격을 할 수 없다는 조건만 붙어있고, 미사일의 개구간 (s,e) 사이의 값이라면 어느 곳이든 가능하다.

아무튼 A 나라에서 미사일을 여러발 쏠 때, 이를 요격할 수 있는 최소한의 미사일 수를 구하는 문제이다. 이런 식으로 B가 최대한 많은 미사일을 요격할 수 있는 x좌표를 구하고, 이를 위해 최소 몇 개의 미사일이 필요한 지에 대해서 구해야 한다.

문제 해결 과정

시도 1. 각 미사일과 길이를 2차원 배열에 기록하기

맨 처음에는 2차원 배열로 기록한 다음에 열마다 확인하려고 했는데, 이 경우에는 targets의 길이가 500,000의 길이까지 커질 수 있고, 개구간 (s,e)는 100,000,000까지 갈 수 있으므로 배열로 풀기에는 너무 많은 메모리와 시간이 소모되어 불가능 할 것 같다.

시도 2. 그리디 알고리즘

최대한 많은 미사일을 한 번에 요격할 수 있어야 한다. 그렇다면 최대한 많은 미사일들이 지나가는 x좌표를 그때마다 선택하게 된다면 최소한으로 필요한 요격 미사일을 구할 수 있을 것 같다. 그렇다면 가장 많은 곳을 지나는 미사일 구간을 어떻게 찾느냐가 문제인데,,, 여전히 1억개의 구성 요소를 지닌 배열을 만들기에는 부담이 있다. 이를 배열이 아닌 다른 방식으로 풀 수 있는 방법이 있을까? 라는 생각에 그냥 처음에 sort로 s를 기준으로 한 오름차순 정렬을 한 뒤에 순차적으로 가면서 최대한 많이 미사일을 요격할 수 있는 방법으로 범위를 조정하면 되지 않을까? 생각했다.

function solution(targets) {
    let missile = 0;
    let start = 0;
    let end = 0;
    targets.sort((a,b) => a[0] - b[0])
    targets.forEach((target) => {
        if(end <= target[0]) {
            missile++;
            start = target[0];
            end = target [1];
        } else{
            if(start < target[0]) start = target[0];
            if(end > target[1]) end = target[1];
        }
    })
    return missile
}

그래서 forEach로 요소들을 돌면서 미사일이 최대한 많이 요격할 수 있도록 미사일이 쏠 수 있는 범위를 start, end 따로 선언하여 미사일을 돌 때마다 조정했으며, 조정할 수 있는 범위를 넘겼을 경우에는 필요한 미사일이 하나 더 추가된다고 판단하여 이 때 미사일의 개수를 올려주었다.

요격성공