[프로그래머스] 요격시스템 - Java

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

프로그래머스

---

1. 문제

폭격 미사일 정수 쌍(s, e) 가 배열로 주어진다. 이에 맞서 요격 미사일을 발사하려고 할 때, 필요한 요격 미사일 개수의 최솟값을 구하는 문제이다. 여기서 s, e는 시작 x좌표 s, 끝 x좌표 e를 의미한다.

 

2. 풀이

그리디 문제이다.

모든 target을 e 기준 오름차순으로 정렬한 후 그리디로 처리한다.

target을 하나하나 보면서

1. targets를 e를 기준으로 오름차순 정렬

2. 1부터 차례대로 볼 때, 시작점보다 작거나 같을 경우 ans++해주고 해당 폭격 미사일의 끝점으로 이동한다.

 

시간복잡도는 Arrays.sort()를 사용하여 최악의 경우 N(50만 log 50만) + for문 O(50만)이 될 것 같다.

 

 

3. 코드

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;
    }
}

4. 사담

재밌었다. 잘못된게 있다면 언제든 피드백 부탁드립니다.