[프로그래머스] (Java) 요격시스템 문제풀이

 

 

📑 1. 문제설명

 
입출력 예 설명

위 그림과 같이 최소 세 번의 요격 미사일 발사로 전부 방어할 수 있다.

 
 

---

💡 2. 접근방식

이 문제는 저번에 풀었던 단속카메라 문제와 비슷하다. 

[프로그래머스] (Java) 단속카메라 (그리디/Greedy)

 
예시 그래프는 각 미사일을 끝점 e 기준으로 오름차순 정렬시킨 모양이다.
그래프에서 (3,7)와 (4,8)은 순서가 잘못되었는데 오류로 추정된다.
단속카메라 문제와 요격시스템 문제의 차이는 끝점 포함 여부이고 둘 다 그리디 알고리즘으로 해결하면 된다.
 

문제 풀이 방법

• 배열을 끝점 기준으로 오름차순 정렬
• 각 미사일의 시작점(s)을 요격 미사일 위치와 비교
• - 시작점이 요격 미사일 위치 이상이면, 새로운 요격 미사일을 발사
• - 요격 미사일 위치를 해당 미사일의 끝점(e)으로 업데이트
• 모든 미사일에 대해 위 과정 반복

📌 개구간 (s, e)이므로 다음 미사일의 시작점이 현재 요격 미사일 위치 이상이면 새로운 요격 미사일 추가
(폐구간 (s, e]이라면 초과일 때만 추가)
 

⭐ 3. 정답코드 (내 코드)

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        Arrays.sort(targets, (o1, o2) -> o1[1] - o2[1]);
        
        int endpoint = 0;
        for (int i = 0; i < targets.length; i++) {
            if(endpoint <= targets[i][0]) {
                endpoint = targets[i][1];
                answer++;
            }
        }
        return answer;
    }
}

---

👏🏻 더 좋은 코드

- 자바에서 정수(int) 연산만 사용하면 개구간을 고려하기 어렵다.
💡 개구간

각 미사일은 (s, e) 로 표현되며, 이는 "s보다 크고 e보다 작은" 구간이다.
이게 무슨 말이냐면 e 위치에서 미사일을 발사하면 해당 미사일을 요격할 수 없다는 뜻이다.
즉, s ≤ x < e 범위에서는 요격할 수 있지만 x == e 위치에서는 요격할 수 없다.

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        // 폭격 미사일 구간을 끝 점을 기준으로 정렬
        Arrays.sort(targets, (a, b) -> Integer.compare(a[1], b[1]));
        
        // 마지막으로 발사된 요격 미사일의 x 좌표
        double lastIntercept = -1.0;
        
        for (int[] target : targets) {
            // 만약 현재 폭격 미사일의 구간에 요격 미사일이 포함되지 않으면
            if (lastIntercept < target[0]) {
                // 새로운 요격 미사일을 발사
                lastIntercept = target[1] - 0.000000001; // 끝 점에서 바로 앞의 실수 위치에 발사
                answer++;
            }
        }
        
        return answer;
    }
}

예를 들어 아래와 같은 미사일 목록이 있다고 가정해 보자.

targets = [[4, 8], [10, 14], [11, 13]]

각 구간을 수직선에 나타내면 아래와 같은 모습이 될 것이다.

4 ------------- 8
                    10 ------------- 14
                        11 ------ 13

여기서 [10, 14] 와 [11, 13] 은 겹쳐 있기 때문에, 11 <= x < 13 구간에서 미사일을 발사하면 두 개를 동시에 요격할 수 있다.
하지만 x = 13 에서 요격하면 [11, 13] 미사일을 요격할 수 없다. 미사일은 13 위치에 떨어지기 때문이다. 
 
⭐ 따라서 끝점 바로 앞의 실수 위치에서 요격 미사일을 발사하는 코드를 쓰면 target[1]보다 아주 조금 앞 위치에서 발사되기 때문에 결국 모든 미사일이 (s, e) 범위 내에서 정상적으로 요격될 수 있다.

double lastIntercept = target[1] - 0.000000001; // 끝 점보다 아주 약간 작은 위치에서 발사