문제링크

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

구현방법

요격 시스템으로 시작 지점보다는 끝지점을 중심으로 요격을 진행을 하면 최소의 미사일을 구할 수 있는 문제였습니다. 백준의 회의실 문제와 비슷한 유형의 문제입니다.

끝지점을 이용하여 정렬을 진행하고 겹치는 부분을 체크하면서 최소의 요격 미사일 개수를 구한다.

구현알고리즘

그리디

CODE

//요격시스템
//생각한 알고리즘 Greedy
// 회의실문제와 비슷함.
//뒷 부분 좌표를 기준으로 정렬하고 그리디 방식
import java.util.Arrays;
import java.util.Comparator;
class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        //미사일 끝 지점 정렬
        Arrays.sort(targets, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int pre = 0;

        for(int idx = 0; idx <targets.length;idx++){
            if(pre <= targets[idx][0]){
                pre = (targets[idx][1]);
                answer++;
            }
        }

        return answer;
    }
}