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

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

프로그래머스

시나리오

1. targets 2차원 배열을 e기준으로 오름차순 정렬

2. 첫 target을 기준으로 잡고 나머지 targets를 순회하며 기준의 end와 현재 target의 start를 비교한다.

3. end가 start보다 크면 continue, 그렇지 않으면 기준을 현재 미사일로 변경하며 요격 미사일 개수++한다.

 

평면좌표상 x축과 평행한 targets를 생각해보자. 기준인 target과 겹치면서 기준의 end보다 끝점이 작은 target은 요격 미사일 한발로 격추가 가능하다. 그렇기 때문에 3과 같은 시나리오가 나온 것이다.

 

그렇다면 기준 target보다 end는 작으면서 겹치지 않는 target의 경우는 어떻게 처리하냐는 의문이 들 수 있는데 이는 시나리오 1로 해결할 수 있다. 애초에 end를 기준으로 오름차순이 되어있으면 순회 시 기준 target의 start보다 작거나 같은 end값을 가진 target이 나올 수가 없다. 바꿔 말하면 기준 target의 end보다 작은 end값을 가지면서 기준 target과 겹치지 않는 target은 기준 target보다 앞에 위치하기 때문에 나올 수 없다는 이야기이다.

 

정답 코드

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        //1. target정렬 e기준 오름차순
        Arrays.sort(targets, (e1,e2)-> e1[1]-e2[1]);
        
        int criteria=0;
        int answer = 0;
        
        //기준 target의 end보다 현재 target의 start가 크거나 같다면 기준을 현재 target으로 바꾸고 answer++
        for(int i=1; i<targets.length; i++){
            if(targets[criteria][1]<=targets[i][0]){
                criteria=i;
                answer++;
            }
        }
        //마지막 요격 미사일 개수 반영
        return ++answer;
    }
}

 

유사 문제

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

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

프로그래머스