프로그래머스-요격시스템

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

문제는 다음과 같다.

문제 해석

이 문제는 2차원 공간에서 미사일이 발사된 범위를 제공하였을 때 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 RETURN 해야 한다고 서술되어 있다. 다음을 그림으로 표현하면 밑의 그림과 같다.

보기 쉽게 띄워놓았지만 개구간이라고 표시했으므로 우리는 이 줄이 전부 일직선에 놓여져 있음을 알아야 한다.

이렇게 범위가 주어졌을 때 겹치는 구간을 확인하여 최소한의 Y축을 긋는 문제이다.

• 이 문제는 스케쥴링 기법과 비슷하다. → 스케쥴링 문제를 참고, 문제풀이

문제 해결

• 끝나는 시점을 오름차순 정렬하여 표현한다.

Arrays.sort(targets, (o1, o2) -> {
            if(o1[1] == o2[1]){
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        });

이렇게 하면 주어진 targets배열을 폐지점이 같을 경우 시구간을 기준으로 정렬하게 하고 폐지점이 다르면 폐지점을 기준으로 정렬하게 한다.

이렇게 정렬한 것을 이제 폐지점을 기준으로 y축을 생성할지 결정해야한다.
즉 targets로 주어진 배열 수만큼 for문을 돌려서 폐지점보다 못하면 y축을 생성하지 않고 폐지점보다 크면 y축을 긋는다.

for(int[] tar : targets){
            if(tar[0] >= end){
                end = tar[1];
                answer++; // 시점이 요격 시스템의 상한보다 오른쪽에 있기 때문에 새로운 요격 시스템 추가
            }
        }

이렇게 하면 요격할 지점의 최소 축의 갯수를 구할 수 있다.

완성 코드

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        Arrays.sort(targets, (o1, o2) -> {
            if(o1[1] == o2[1]){
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        });
        
        int end = targets[0][1];
        answer++; // 첫 번째로 만들어지는 요격 시스템
        
        for(int[] tar : targets){
            if(tar[0] >= end){
                end = tar[1];
                answer++; // 시점이 요격 시스템의 상한보다 오른쪽에 있기 때문에 새로운 요격 시스템 추가
            }
        }
        
        return answer;
    }
}