[프로그래머스] 요격 시스템(JAVA)

문제

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

---

풀이(16분)

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int[][] targets) {
        // e 오름차순 정렬
        Arrays.sort(targets, (o1, o2) -> o1[1] - o2[1]);
        
        int ans = 0;
        int x = 0;
        for (int[] target : targets) {
            if (x <= target[0]) {
                x = target[1];
                ans++;
            }
        }
        
        return ans;
    }
}

---

문제 풀이 전략

 

괜히 어렵게 생각하느라 시간을 좀 쓴 문제이다.

풀이 방법은 간단하다.

 

1. 끝점을 기준으로 오름차순 정렬을 한다.

2. 정렬된 것 들의 끝 - 0.5 포인트에서 요격을 한다고 생각하자.

 

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

 

예를 들면 다음과 같다. 이 문제에서 끝 점을 기준으로 정렬을 했다고 생각해 보자.

그렇다면 아마 [1,3] [4,5] [3,7] [4,8] [5,12] [11,13] [10,14]가 된다.

1. 그렇다면 2.5에서 먼저 한 발을 쏜다. x = 2.5로 업데이트한다.

2. [4,5]는 2.5에서 쏜 것으로 없어지지 않으므로 4.5에서 또 쏜다.  x = 4.5로 업데이트한다.

3. [3,7]은 3 < 4.5이므로 자동으로 제거된다.

 

이런 식이 되는 것이다!