[프로그래머스] 요격 시스템 Lv2 JAVA [그리디][엄탱]

문제 링크

프로그래머스

문제 설명

문제는 길기 때문에 링크를 통해서 보는 것을 추천한다.

요약하자면, 가로 방향으로 발사되는 적 미사일을  세로 방향으로 발사되고 관통되는 미사일을 이용해 요격하여 모든 적 미사일을 파괴할 것이다. 이때 최소로 필요하는 요격 미사일 개수를 구하면 되는 문제다.

 

 

입출력 예 설명 사진 - 프로그래머스 출처

 

해설

해당 문제는 그리디 문제이며, 정렬을 필요로 하는 문제이다. 그리디 문제는 정렬이 중요한 문제가 많은 것 같다.

정렬과 그리디를 합쳐서 풀어내는 문제는 내가 풀어본 문제 중에서는 기준을 잘 정해야 하는 것 같다. 

해당 문제는 두 가지 정도 알면 좋다.

 

1. 정렬 기준은 '시작 구간' 이든 '끝나는 구간'이든 하나의 기준으로 오름차순 해주면 된다.

몇몇 블로그에는 끝나는 구간을 기준으로만 잡았는데 시작 구간도 괜찮고 끝나는 구간도 괜찮다. 다만, 그에 맞게 풀어내기만 하면 된다. 나는 시작 구간을 기준으로 오름차순 했는데 다른 이유는 없고 그냥 생각하기 편하고 쉬워서 기준으로 잡았다.

 

2. 미사일 구간을 동적으로 잘 설정하는게 중요하다.

요격 구간은 계속 변경되는데, 시작 구간은 최대, 끝 구간은 최소인 구간으로 잡아야 한다. 

아래 예시 사진을 살펴보자.

 

 

요격 구간 참고 사진

 

 

요격 구간을 변경하지 않는다면, 1번 구간을 기준으로 요격 미사일을 발사했다고 가정하고 요격 구간을 변경하지 않으면 하나의 미사일로 1번 2번 3번 모두 격추할 수 있기 때문에 올바르지 않다.

요격 구간을 동적으로 변경한다면, 1번 구간을 하나의 요격 미사일로 격추할 수 있는걸 확인하고 2번 구간을 확인하고 2번에 맞게 구간을 수정하면 3번은 맞출 수 없는 미사일이 되기 때문에 올바른 방법이다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        Arrays.sort(targets, ((x, y) -> x[0] - y[0]));
        
        int preStart = targets[0][0];
        int preEnd = targets[0][1];
            
        for (int[] target : targets) {
            if (answer == 0) {
                answer += 1;
                continue;
            }
            
            int curStart = target[0];
            int curEnd = target[1];
            
            if (preStart <= curStart && curStart < preEnd) {
            	// 요격 구간이 계속 변경
                // 시작 구간은 더 큰 값을 기준으로 변경
                // 끝 구간은 더 작은 값을 기준으로 변경 합니다.
                preStart = Math.max(preStart, curStart);
                preEnd = Math.min(preEnd, curEnd);
            } else {
                preStart = curStart;
                preEnd = curEnd;
                answer += 1;
            }        
        }
    
        return answer;
    }
}