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

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

프로그래머스

 

 

 

 

 

문제

• 발사한 미사일은 x축에 평행한 직선 형태의 모양이며 정수 쌍 (s, e) 형태로 표현됨
• y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있음
• 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습
• 각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값 구하기

 

제한 사항

• 1 ≤ targets의 길이 ≤ 500,000
• targets의 각 행은 [s,e] 형태
• 0 ≤ s < e ≤ 100,000,000

 

출처 : 프로그래머스 문제 (https://school.programmers.co.kr/learn/courses/30/lessons/181188)

 

 

 

 

 

풀이

 예시로 나온 그림을 보니 회의실 문제(https://www.acmicpc.net/problem/1931)가 생각이 났다. 

회의실 문제는 회의 시작 시간과 끝나는 시간이 주어질 때, 최대 사용할 수 있는 회의의 최대 개수를 구하는 문제이다. 하지만 이 문제에서는 최솟값을 구하는 것이다.

 

접근법은 그리디로 유사할 것 같았고, 미사일 시작 지점을 기준으로 오름차순 정렬을 해봤다.

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

 

그리고 미사일 종료시점이 다음 미사일 시작시점보다 작거나 같은지 확인하고, 기준점을 갱신하고, 미사일을 요격하는 시점으로 삼았다.

 

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

 

이렇게 3개가 나온다.

 

 

하지만 모든 테스트 케이스를 통과하지 못했다!

 

 

미사일 종료 지점을 기준으로 오름차순 정렬을 해봤다.

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

 

똑같이 3개가 나오는데, 미사일을 요격하는 지점이 다르다.

 

 

 

결국 회의실 문제와 똑같은 풀이이다. (https://programmingiraffe.tistory.com/57)

 

 

 

 

 

코드

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        //1. 미사일 종료지점(e)을 기준으로 오름차순 정렬
        Arrays.sort(targets, (o1, o2) -> o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1]);
        
        int prev_end = 0; //기준 : 미사일 종료시점(e)
        int answer = 0; //필요한 요격 미사일 수
        
        //2. 미사일 시작지점이 기준보다 같거나 크면 갱신
        for(int i = 0; i < targets.length; i++) {
            if(targets[i][0] >= prev_end) {
                prev_end = targets[i][1];
                answer++;
            }
        }
        
        return answer;
    }
}

 

 

 

 

 

결과

 

 

 

 

 

 

배운점

• 2차원 배열 정렬에 람다식 사용
• 정렬 기준에 따라 결과는 다르다