[프로그래머스] 요격 시스템 / 자바(Java)

• 문제

• 해설

• 주의점

• 코드

문제

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

프로그래머스

 

---

해설

가로 방향으로 발사되는 적 미사일을  세로 방향으로 발사되고 관통되는 미사일을 이용해 요격하여 모든 적 미사일을 파괴할 것입니다. 이때 최소로 필요하는 요격 미사일 개수를 구하면 되는 문제입니다.

 

타겟의 갯수가 500,000개로 각각의 수를 알아보기는 너무 많아 그리디 방식으로 해결방향을 잡습니다.

입출력 예 설명 사진  (출처 - 프로그래머스)

모든 타겟을 맞추어야 함으로 특정 기준으로 정렬하여 한 타겟의 범위에 포함되는 타겟을 제외하며 갯수를 더해봅니다.예를 들어 시작점 기준 내림차순으로 정렬을 한다면 2,1,3,4순으로 정렬이 됩니다.이때 2의 범위에 포함되는 타겟들을 제외시키기 위해 2의 시작 시점을 구합니다.시작시점 내림차순이 되어있으므로 다른 타겟들은 2보다 더 빨리 시작되었을 것이고, 만약 2의 시작시점보다 특정 타겟의 끝시점이 크다면 2와 함께 격추가능한 경우로 보고 제외할 수 있습니다.

특정 타겟의 시작시점  <<  2의 시작시점  <<  특정 타겟의 끝시점(변경가능값)

이를 바탕으로 예시에서는 1과 3이 2의 범위안에 들어 같이 격추됩니다.이후 4번의 끝시점은 2의 시작지점보다 빨라 2의 범위안에서 벗어나며 새로운 격추미사일이 필요해 4번의 시작지점을 저장하고 반복합니다.

 

주의점

• 개구간이기 때문에 범위의 끝 부분을 주의해야 한다.

---

코드

import java.util.*;
class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        // 각 타겟들을 시작시간기준 내림차순 정렬
        Arrays.sort(targets, (o1,o2)->o2[0]-o1[0]);
        
        int start_range = targets[0][0];
        answer++;
        
        // 각 타겟의 끝 시간과 기준 시작시간을 비교 
        for(int[] t : targets){
            if(start_range>=t[1]){
                start_range = t[0];
                answer++;
            }
        }
        return answer;
    }
}