(Java) 프로그래머스 - 미사일 요격

오랜만에 풀어보는 알고리즘 문제였다.

왠지 문제가 그리디하게 접근하면 풀릴것 같아서 시도했더니 한시간만에 풀 수 있었다.

---

로직

첫번째로 targets 배열을 정렬해야 한다.

어떤 기준으로 정렬하냐가 중요한데, 나는 s를 오름차순으로 정렬했다가 최솟값에 맞지 않는다는 것을 깨닫고

e을 오름차순으로 정렬했다.

 

for문을 돌며 미사일이 날아오면 미사일의 시작지점인 s와 e중 한 지점에서 요격해야 한다.

미사일 하나에 맞춰서 요격을 하고 다음 미사일이 현재 요격 기준에 맞지 않으면

answer를 추가하고 요격 기준을 갱신하는 방식으로 생각하면 된다.

 

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        int end = 0;
        
        Arrays.sort(targets, Comparator.comparingInt(o -> o[1]));

        for(int i = 0; i < targets.length; i++) {
            int s = targets[i][0];
            int e = targets[i][1];
            
            if(s >= end) {
                end = e;
                answer++;
            }
        }
        
        return answer;
    }
}