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

그리디 문제입니다.

 

문제를 요약하면 다음과 같습니다.

• 여러 개의 직선이 주어질 때, 모든 선을 지나도록 하는 최소 직선의 개수를 구하라

문제에서 주어지는 예제는 다음과 같습니다.

주어지는 직선은 주황색 직선입니다. 이 모든 주황색 직선을 지나도록하는 선은 위 그림과 같이 최소 세 개가 필요합니다.

 

어디선가 많이 보던 내용 아닌가요?

네, 스케쥴링 문제와 매우 유사합니다.

스케쥴링 문제와 비슷하게 끝나는 시간을 기준으로 오름차순을 하고, 반복을 하면서 시점과 종점을 비교하면 됩니다.

 

이와 비슷한 문제로 백준의 회의실 배정 문제가 있습니다.

스케쥴링을 연습하실 분은 아래 링크를 통해 가셔서 풀어보시길 바랍니다.

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

 

[구현 코드]

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