[프로그래머스] Lv.2 요격시스템 (Java)

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

프로그래머스

 

Lv.2 요격시스템

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        Arrays.sort(targets, (a1, a2) -> a1[1] - a2[1]);

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

---

핵심 정리1

그리디 방식으로 해결해야 하며, 겹치는 구간을 하나의 미사일로 커버하고, 최소 개수로 요격한다는 점을 이용해야 한다.

 

1. 끝점 기준 오름차순 정렬

Arrays.sort(targets, (a1, a2) -> a1[1] - a2[1]);

빨리 끝나는 구간부터 처리해야 최적

2. 기준점 Before 유지

int before = 0;

마지막으로 쏜 미사일 위치

3. 안 겹치면 미사일 추가

if (before <= targets[i][0]) {
    before = targets[i][1];
    answer++;
}

 

• before <= 시작점: 기존 미사일로 커버 불가
• 그래서 새 미사일 발사
• 발사 위치 = 해당 구간의 끝점