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

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

프로그래머스

 

사용 알고리즘

• 그리디 알고리즘
• 정렬

풀이

import java.util.*;
class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        Arrays.sort(targets, (a,b) -> a[1] - b[1]);
        int before = 0;
        for(int [] target : targets) {
            
            if (before > target[0]) continue; 
            before = target[1]; 
            answer++;
        }
        return answer;
    }
}

문제 회고

 

처음에 이분탐색을 써야하나? 고민하다가 그리디로 푸는 것을 꺠달았다.

 

이전 미사일의 끝점과 다음 미사일의 시작점이 겹쳐야 한번의 요격 미사일로 방어할 수 있다.

 

우선, 미사일의 좌표는 [s,e] 형태로 되어있는데, s는 시작점, e는 끝점이다. 끝점을 기준으로 정렬을 수행하게 되면 밑 그림에서 (4,8)과 (3,7) 위치만 바뀌게 된다.

 

 

2차원 배열을 순회하면서, before 값에 끝 점을 업데이트 해준다. 그리고 미사일 count를 1 증가시켜준다.

 

[1,4]에서, before는 4가 되고, count는 1이 된다.

 

[4,5] -> before = 5, count = 2

[3,7] -> before = 5, target[0] = 3 이므로 continue

[4,8] -> before > target[0]에서 5 > 4 이므로 continue

 

[5,12] -> before = 12, count = 3

[11,13] -> 12 > 11,  continue

[10,14]  -> 12 > 10, continue

 

끝 점을 기준으로 정렬 -> 순회하며 끝점과 시작점을 비교 

 

이 두가지 로직이 핵심이라고 보면 된다.