🎯문제
A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다.
A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다.
A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다.
각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
제한 사항
- 1 ≤ targets의 길이 ≤ 500,000
- targets의 각 행은 [s,e] 형태입니다.
- 이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야 합니다.
- 0 ≤ s < e ≤ 100,000,000
입출력 예
| targets | result |
|---|---|
| [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]] | 3 |
입출력 예 설명
위 그림과 같이 최소 세 번의 요격 미사일 발사로 전부 방어할 수 있습니다.
✏️풀이
코드
import java.util.*;
class Solution {
public int solution(int[][] targets) {
int answer = 0;
// 끝나는 순서가 빠른 것부터
// 끝나는 순서가 동일하다면 시작하는 순서가 빠른 것 부터
// 배열을 정렬
Arrays.sort(targets, (o1, o2) -> o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1]);
// 맨 먼저 끝나는 값을 end에 저장
int end = targets[0][1];
// 요격 시스템 하나 추가
answer++;
// 배열의 값을 하나씩 불러옴
for(int[] temp : targets) {
// 현재 end보다 늦게 시작한다면
if(temp[0] >= end) {
// end를 바꿔주고
end = temp[1];
// 새로운 요격 시스템 추가
answer++;
}
}
return answer;
}
}설명
배열의 정렬을 사용해서 진행하였다.
targets 배열에는 (s, e)의 값이 들어있다. 여러 미사일의 개수와 각각 미사일의 시작, 종료 시간을 뜻하는 것인데, 이때 이 e인 끝나는 순서가 빠른 것부터 정렬을 진행한다. 만약 끝나는 순서가 동일하다면 s인 시작하는 순서가 빠른 것부터 배열을 정렬해준다.
그렇다면 targets[0][1]에는 맨 처음 끝나는 값이 저장되어 있을 것이다.
이 맨 처음 끝나기 전에 요격 시스템 하나가 무조건적으로 필요하기 때문에 answer를 하나 증가해준다.
이후 for-each문을 통해 배열을 하나씩 불러온다. 이때 비교를 진행하는 것은 end에 저장된 값과 시작하는 값이다. 만약 end보다 먼저 시작한다면 한번의 요격 시스템으로 처리할 수 있으나 end와 같거나 늦게 시작한다면 새로운 요격 시스템이 필요하다. 따라서 end보다 늦거나 같게 시작한다면 end 변수의 값을 바꿔주고 answer를 하나 증가시켜준다.
위의 과정을 반복하고 끝난 뒤에 answer를 반환해준다면 문제를 해결할 수 있다!
💡느낀 점
이번 문제는 스케줄링 문제와 매우 흡사했다. 배열의 정렬만 잘해준다면 요격 시스템의 최솟값을 구할 수 있었다. 맨 처음 프로그래머스를 풀기 시작했을 때는 배열을 정렬하는 것도 매우 어려워했는데, 요즘 문제들에서는 배열의 정렬은 기본으로 해야하기 때문에 많은 연습이 된 것 같다. 이번 문제를 풀면서 순식간에 배열 정렬을 생각해서 코드를 짜려고 하는 모습을 보고 특히 더 느끼게 되었다 :)
링크
