[프로그래머스] Level 2. 요격연습 - JAVA

🔗 문제

프로그래머스

 

👨🏻‍💻 풀이 및 코드

문제 유형 및 난이도 :  그리디 / Level 2

 

풀이

미사일을 시작 순으로 정렬하는 방법과 끝나는 시점 순으로 정렬하는 방법 2가지로 풀었다.

 

---

전체 코드

Sol1)

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        Arrays.sort(targets, (o1, o2) -> (o1[0] - o2[0]));  // s 오름차순으로 정렬
        int cnt = 0;
        int last = -1;  // 커버할 수 있는 범위
        
        for(int[] target: targets) {
            if(last <= target[0]) {     	// 새 요격기 필요
                cnt++;
                last = target[1];
            } else if (target[1] < last) {  // 더 작은 범위 커버
                last = target[1];
            }
        }
        
        return cnt;
    }
}

 

Sol2)

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        Arrays.sort(targets, (o1, o2) -> (o1[1] - o2[1]));  	// e 오름차순으로 정렬
        
        int cnt = 0;
        int idx = 0;
        int end = -1;
        
        while(idx < targets.length) {
            cnt++;
            end = targets[idx][1];
            
            while(idx < targets.length && targets[idx][0] < end) {	// 현재 요격기로 커버 가능
                idx++;
            }
        }
        
        return cnt;
    }
}