프로그래머스 Lv2 - 요격 시스템

 

문제

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

프로그래머스

풀이시간 : 92분

시도 횟수 : 2

복기

예전에 비슷한 유형의 문제를 풀어봤음에도 불구하고, 풀이가 오래 걸렸다.

풀이에 대한 확신없이 로직을 만들어 통과하였는데, 풀이에 대한 근거를 확보하는것이 어려워 이부분 보충이 필요하다.

 

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int N = targets.length;
        Arrays.sort(
          targets,
          (first, second) -> {
            if(first[0] == second[0]){
              return second[1] - first[1];
            }
            
            return first[0] - second[0];
          }
        );
        
        int answer = 0;
        int right = -1;
        for (int i = 0 ; i < N ; i ++){
            if(targets[i][0] < right){
                if(targets[i][1] < right){
                    right = targets[i][1];        
                }
                continue;
            }

            right = targets[i][1];
            answer++;
        }
        
        return answer;
    }
}

 

더 나은 풀이 방법

X 정렬 풀이 방법

나는 X 정렬 풀이방법이었으며, 이 사람은 좀 더 간단한 로직으로 기술하였다.

나는 정렬할때 Y 측 기준도 고려하였지만, 로직에서 중요한 부분이 아니었다.

결국 근거없는 불필요한 로직이였던 셈이다.

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        Arrays.sort(targets, (a, b) -> a[0] - b[0]); // x좌표 기준으로 정렬
        int cnt = 0;
        int last = -1;
        for (int i = 0; i < targets.length; i++) {
            int[] missile = targets[i];
            if (missile[0] > last) { // 새로운 요격 미사일 필요
                cnt++;
                last = missile[1] - 1; // 해당 미사일로 커버되는 범위
            } else if (missile[1] - 1 < last) { // 더 작은 범위로 커버 가능한 미사일 필요
                last = missile[1] - 1; // 해당 미사일로 커버되는 범위
            }
        }
        return cnt;
    }
}

 

Y  정렬 풀이 방법

이 풀이 방법이 최선의 방법이라 생각한다.

Y 오름차순 정렬하여, lastE를 갱신할 필요가 없어진다.

따라서 lastE의 범위를 넘는순간 새로운 미사일이 필요하다.

import java.util.*;
class Solution {
    //* target -> [s, e]
    public int solution(int[][] targets) {
        int answer = 0;

        //* e 기준 정렬
        Arrays.sort(targets, (o1, o2) -> o1[1] - o2[1]);

        int lastE = targets[0][1];
        for(int[] target : targets){
            //* 미사일의 Start가 E 밖에 있다.

            if(target[0] >= lastE){
                answer++;
                lastE = target[1];
            }
        }
        answer++;

        return answer;
    }
}

 

풀이에 대한 근거 확보하기

하나의 요격 미사일로 매번 최대한 많은 미사일을 요격해야, 최소로 요격미사일을 사용할 수 있다.

그렇기 때문에 Y기준으로 정렬한 후, 최대한 많은 미사일을 부수는 구간을 찾아나가면 된다.