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

문제 링크

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

프로그래머스

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 이차원 배열을 정렬 (시작과 끝이 빠른 순서로)
2. 0번째 요소의 시작과 끝을 s와 e로 지정
3. 이후 뒤에 배열을 돌며, 뒤의 요소의 시작과 끝이 현재 s와 e 범위 내에 들어온다면 해당 요소를 넘어감
   1) 단 현재의 s보다 요소의 시작이 더 크면 s를 해당 값으로 초기화, 현재의 e보다 요소의 끝이 더 작으면 e를 해당 값으로 초기화
4. 만약 해당 범위 밖의 요소라면, 답을 +1 한 후 현재 s와 e를 해당 요소 시작과 끝으로 초기화

 문제의 해결 방식은 그리디하게 풀면 된다. 문제의 요지는 전체 폭격 미사일들을 최소의 미사일 개수로 막아내야 하는 문제이다. 단순히 이렇게만 보았을 때는 최적의 값을 찾기 위해 다양한 부분을 고려해야할 것 같지만, 다르게 생각해볼 수 있다.
 결국 하나의 폭격 미사일 범위가 있다면, 해당 미사일을 막기 위해선 결국 하나의 미사일을 사용해야만 한다. 그러한 상황에서 가장 효과적으로 미사일을 사용하려면, 해당 범위 내에 겹치는 미사일들을 최대한 찾아서 제거해주면 되는 방식이다. 또한 미사일을 따질 때 아무 폭격 미사일의 범위부터 시작이 아니라, 가장 먼저 오게 되는 폭격 미사일을 시작으로 탐색을 반복하면 문제를 쉽게 해결할 수 있다.

 이를 위해 주어진 이차원 배열을 정렬하여 시작과 끝이 가장 빠른 배열들이 먼저 오도록 한다. 이후 0번째 요소의 시작과 끝을 각각 s와 e로 설정한 다음 이후 배열을 돌며 탐색을 반복한다. 만약 그 다음 오는 폭격 미사일의 범위가 현재 s~e에 포함된다면 하나의 미사일로 한 번에 터트릴 수 있기 때문에 이를 넘어간다. 다만 이들을 같이 처리하기 위해선 겹치는 부분만이 범위가 되기 때문에, 이를 위해 s와 e를 좁혀주는 작업을 진행한다. 이와 반대로 만약 그 다음 오는 폭격 미사일의 범위가 s~e밖이라면, 현재 미사일로는 처리할 수 없기 때문에 새로운 미사일을 사용해야 해서 answer에 +1을 해주고, 해당 범위를 s와 e로 새로 초기화 해준다.
 더불어 해당 문제의 경우, 이차원 배열을 정렬하여 푸는 방식과, 주어진 이차원 배열 속 하나의 폭격 미사일 범위를 객체로 변환하여 우선순위 큐를 활용해 푸는 방식이 있다.

 

class Solution {
    public int solution(int[][] targets) {
        int answer = 1, s, e;

        //풀이 1 => 단순 이차원 배열 정렬
         Arrays.sort(targets, (o1, o2) -> {//이차원 배열 정렬
             if(o1[0]==o2[0]){
                 return o1[1] - o2[1];
             }
             return o1[0] - o2[0];
         });

         //시작 요소를 s와 e로 초기화 
         s = targets[0][0];
         e = targets[0][1];

         for(int i=1;i<targets.length;i++){//이후 배열을 돌며
             if(targets[i][0]<e){//현재 s~e 범위내라면
                 s = Math.max(s, targets[i][0]);
                 e = Math.min(e, targets[i][1]);
             }else{//현재 범위 밖이라면
                 ++answer;
                 s = targets[i][0];
                 e = targets[i][1];
             }
         }

        return answer;
    }
}

class Solution {
    public int solution(int[][] targets) {
        int answer = 1, s, e;

         //풀이 2 => 우선순위 큐 활용
         PriorityQueue<Infor> pq = new PriorityQueue<>();
         for(int i=0;i<targets.length;i++){
             pq.add(new Infor(targets[i][0], targets[i][1]));
         }

         Infor start = pq.poll();
         s = start.s;
         e = start.e;

         while(!pq.isEmpty()){
             Infor now = pq.poll();
             if(now.s < e){
                 s = Math.max(s, now.s);
                 e = Math.min(e, now.e);
             }else{
                 ++answer;
                 s = now.s;
                 e = now.e;
             }
         }
         return answer;
    }

    class Infor implements Comparable<Infor>{
        int s, e;

        public Infor(int s, int e) {
            this.s = s;
            this.e = e;
        }

        @Override
        public int compareTo(Infor o){//시작과 끝이 더 빠른 순으로
            if(this.s == o.s){
                return this.e - o.e;
            }
            return this.s - o.s;
        }
    }
}

결과