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

<문제>

• https://school.programmers.co.kr/learn/courses/30/lessons/181188
• A나라가 B나라 침공, A나라에 대항하여 요격하려고 함, 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 함
• 이 세계는 2차원 공간
  • A 나라: 발사한 폭격 미사일은 x 축에 평행한 직선 모양, 개구간-정수 쌍 (s, e) 형태
  • B 나라: 특정 x 좌표에서 y 축에 수평 발사, 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격 가능
    • 실수인 x좌표에서도 발사 가능, 단 (s, e) 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격X

<입력>

• 2차원 배열(targets) - 각 폭격 미사일의 x 좌표 범위 목록

<출력>

• 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값 return

  targets	result
  [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]	3

  

<제한사항>

• 1 ≤ targets의 길이 ≤ 500,000
• targets의 각 행은 [s,e] 형태입니다.
  • 이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야 합니다.
  • 0 ≤ s < e ≤ 100,000,000

<풀이>

1. 오름차순 정렬(e기준) - 이걸 알면 문제는 바로 풀린다.
2. 앞의 e와 뒤의 s를 비교
   1. e>s : 다음 것으로 넘어가기
   2. e<s : +1후 비교 시작
   3. e==s : +1후 비교 시작
   첫번째 예제 풀이

<전체코드>

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        Arrays.sort(targets, (o1,o2)->o1[1]-o2[1]); //e 기준 오름차순 정렬
        int t = 0;
        for(int i=0; i<targets.length; i++) {
            if(t <= targets[i][0]) {
                t = targets[i][1];
                answer++;
            }
        }
        return answer;
    }
}