[Algorithm] 요격 시스템 - JavaScript

프로그래머스 - 요격 시스템
난이도 : Level 2
정답률 : 33%

▶ 문제

▶ 풀이

시작 좌표가 작은 순으로 정렬 후 끝 좌표가 다음 미사일의 첫 부분보다 작으면, 다음 미사일의 끝으로 좌표를 설정 후 카운트를 추가한다.

function solution(targets) {
    var answer = 1;
    // 스타트 지점이 작은 기준으로 정렬한다
    targets.sort((s,e) => s[0] - e[0]);
    // 정렬된 미사일에 최종 지점을 기준으로 시작한다.
    let loc = targets[0][1];
    targets.forEach(mi => {
        // 시작 좌표가 지정된 좌표보다 작을 경우 중
        if(mi[0] < loc) {
            // 마지막 좌표가 지정된 좌표보다 작을 경우
            if (mi[1] < loc) {
                // 좌표를 재설정한다.
                loc = mi[1];
            }
        // 시작 좌표가 지정된 좌표보다 크거나 같을 경우에 카운트를 올린다
        }  else {
                loc = mi[1]
                answer++;
            }
    })
    return answer;
}

▶ 삽질

• 첫번째 미사일(s)와 두번째 미사일(e)의 차가 1일 경우 발사할 미사일의 좌표는 s + e / 2 로 고정이다.
  미사일 간의 차가 1일 경우의 발사할 미사일을 고정해두고 차가 클 경우 이미 배열에 있는 곳을 제거하고 추가하면 되지 않을까?

-> 두 차이를 기준으로 로직을 짤 경우 차가 2 이상일 때는 발사해야 하는 가장 효율적인 지점을 알 수 없다.

• targets 배열의 가장 큰 수와 가장 작은 수의 간격들을 모두 배열에 추가하고 그 중 가장 많이 겹치는 부분을 제외한 나머지는 제거하면 되지 않을까?

-> 획기적으로 잘못된 발상이었다. 반복문을 모든 간격에서 돌려야 하기에 불필요한 연산이 너무 많이 생긴다.

▶ 다른 풀이

나와 비슷한 풀이가 많았다.
그 중 미사일의 마지막 부분에 0.5 를 빼거나 추가하는 풀이들이 종종 보였는데, 아마 나처럼 입출력 그래프 예시를 보고 간격에서 x축이 숫자와 숫자 사이라는 발상을 떠올린 것 같다.

   targets.forEach(target => {  
        if(currentMax === -1) {
            currentMax = target[1];
            return;
        } 
        if(target[0] >= currentMax) {
            currentMax = target[1];
            result++;
            return;
       }
    });

* else 를 쓰지 않고 조건문을 탈출하는 풀이가 인상적이었다.

▶ 고찰

입출력 예시 그래프를 보고 targets에 x축이 고정되었다고 믿어 sort 해야 한다는 생각을 하기까지 오래 걸렸다. 데이터를 유연하게 바라볼 필요가 있다.