프로그래머스 요격 시스템 (java) 그리디

프로그래머스 요격시스템 JAVA

---

관찰

이 문제를 정말 오래 생각했다.. 유니온 파인드인지, 파라메트릭 서치인지, HashMap을 써야 하는지 많은 고민을 했는데 결국 그리디 문제였다.. 그리디 문제를 사실 잘 안풀어서 혼난 것 같습니다..ㅠ

규칙을 설명하자면 구간의 끝점을 기준으로 정렬한 다음, 끝점에서 요격을 하는 식으로 진행을 하면 최소 횟수로 요격 시스템을 굴릴 수 있다

즉, 끝점이 가장 작은 친구를 요격했을 때 시작점이 포함된 친구들까지 다 요격을 시키고 그 다음으로 끝점이 가장 작은 친구를 요격하면서 최소값을 찾는 로직

---

정답 코드

import java.io.*;
import java.util.*;
class Solution {
    static int n;
    public int solution(int[][] targets) {
        int answer = 0;
        
        n = targets.length;
        Arrays.sort(targets, (a ,b) -> Integer.compare(a[1], b[1]));
        
        int lastPoint = 0;
        for(int i=0;i<n;i++){
            if(targets[i][0] < lastPoint) continue;
            answer++;
            lastPoint = targets[i][1];
            
        }
        
        return answer;
    }
}

---

풀이

1. targets를 람다식을 활용한 Arrays.sort로 끝 점을 기준으로 오름차순 정렬한다.

2. 끝 점 기준을 정한 뒤 정렬된 targets를 요격한다.

3. 요격을 하면서 끝 점을 갱신하고 시작점이 그보다 앞에 있는 것들은 요격되었으니 넘어간다.

4. 요격하는 횟수를 세어준다.

---

마무리

일단 이 문제를 처음 접근하면서 완전 탐색의 방법이 떠오르지 않았다. 원래 완전탐색 방식을 떠올린 후 전처리를 하던 dp를 하던 풀어야 하는데 쉽지 않았던 것 같다.

완전탐색이 떠오르지 않을 정도로 문제가 의심스럽다면 그리디를 떠올려보자