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

🔗 요격 시스템

 

A 나라의 폭격 미사일은 2차원 공간에서 x축에 평행한 직선 형태로 표현된다. B 나라에서는 x축의 특정 좌표에서 y축에 수평한 미사일을 발사해 폭격 미사일을 요격할 수 있다. 하지만 요격 미사일을 최소한으로 사용해야 한다. 주어진 폭격 미사일의 x 좌표 범위 목록을 통해 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 구하는 문제이다.

 

=> 각 폭격 미사일의 x 좌표 범위가 주어졌을 때, 여러 폭격 미사일이 겹치는 구간에 대해 하나의 요격 미사일로 여러 개의 폭격 미사일을 동시에 요격할 수 있다. 목표는 이러한 겹치는 구간을 고려해 요격 미사일의 발사 횟수를 최소화하는 것이다.

 

=> 그림에서 가로선은 폭격 미사일(targets), 세로선은 요격 미사일을 뜻한다. 이 가로선들을 통과하는 최소의 세로선 수를 return하면 된다.

 

🥊 접근 방법 🥊

비슷한 문제를 풀어본 적이 있기 때문에 끝나는 지점을 기준으로 정렬한 뒤, 시작시간을 비교하면 되겠다고 생각했다.

 

1. 정렬

폭격 미사일의 범위를 '끝나는 지점'을 기준으로 오름차순 정렬한다. 가장 먼저 끝나는 미사일부터 요격 미사일을 발사해야 이후에 나오는 미사일을 최대한 많이 커버할 수 있기 때문이다.

Arrays.sort(targets, (o1, o2) -> o1[1] - o2[1]);

 

 

2. 발사

• curr : 현재 요격 미사일이 도달할 수 있는 x 좌표

각 폭격 미사일의 시작 지점이 curr보다 큰 경우에만 새로운 요격 미사일을 발사한다. 이때 curr을 해당 폭격 미사일의 끝나는 지점으로 업데이트한다.

for(int[] target : targets){
    if(curr <= target[0]) {  // 각 폭격 미사일의 시작 지점이 현재 범위보다 큰 경우 새로운 미사일 발사
        curr = target[1];  // 현재 범위는 폭격 미사일의 끝나는 지점으로 업데이트
        answer++;  // 미사일 개수 증가
    }
}

 

✨ 전체코드 ✨

• target : 각 폭격 미사일의 x 좌표 범위 목록

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        int curr = 0;
        
        Arrays.sort(targets, (o1, o2) -> o1[1] - o2[1]);
        for(int[] target : targets){
            if(curr <= target[0]) {
                curr = target[1];
                answer++;
            }
        } return answer;
    }
}

 

🌀 성능

• 메모리 : 74.9 MB
• 시간 : 0.42 ms

 

🥕 비슷한 문제

• 백준 회의실 배정