🤔 문제
🔗
각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
💡 풀이과정
특정 범위에 있는 폭격 미사일을 요격하는 미사일의 개수를 나타내는 문제이다.
구조를 그림으로 나타내면 다음과 같다.
폭격 미사일 배열을 순회해 기존에 있는 요격 미사일로 폭격 가능한지 따지는 방법으로 풀 수 있다.
폭격 가능할 경우 필요에 따라 요격 미사일의 요격 범위 (s, e)를 수정해준다.
폭격 불가능할 경우 새로운 요격 미사일을 추가하는 방식으로 풀면 된다.
하지만 폭격 미사일 배열을 그대로 사용하면, s 좌표와 e 좌표를 모두 고려해주어야 하므로 복잡하다.
그렇다면 배열을 정렬해주면 어떨까?
배열을 뒤쪽에 맞추어 정렬해보자.
폭격 미사일의 e 좌표는 반드시 직전 미사일을 폭격한 요격 미사일의 e 좌표보다 작을 수밖에 없다.
따라서 s 좌표만을 고려해 문제를 풀면 된다.
미사일의 좌표 정보를 저장할 Target 클래스를 만들고 Comparable<T>을 구현해 정렬기준을 만들어주었다.
class Target implements Comparable<Target> {
int x1;
int x2;
public Target(int x1, int x2) {
this.x1 = x1;
this.x2 = x2;
}
@Override
public int compareTo(Target t) {
if(this.x2==t.x2) return t.x1-this.x1;
else return t.x2-this.x2;
}
}
x1은 범위의 s 좌표, x2는 e 좌표이다.
x2가 같을 경우 x1을 비교해 범위가 더 넓은 폭격 미사일을 앞쪽에 배치해준다.
이제 미사일에 대한 Target 인스턴스를 생성하고 ArrayList에 담아 정렬한다.
ArrayList<Target> targetList = new ArrayList();
for(int[] t : targets) {
Target target = new Target(t[0], t[1]);
targetList.add(target);
}
Collections.sort(targetList);
x1은 요격 미사일의 e 좌표를 나타내는 변수이다.
폭격 미사일의 범위가 좌표 범위가 0≤s<e≤100,000,000이므로, x1을 100,000,000으로 설정해주었다.
answer은 요격 미사일의 개수를 나타내는 변수이다.
int x1 = 100000000;
int answer = 0;
이제 폭격 미사일 리스트를 순회하여 필요한 요격 미사일 개수를 계산한다.
고려해야 할 사항은 다음과 같다.
- 기존 요격 미사일로 타격 가능한 경우
폭격 미사일의 e 좌표가 새로운 x1이 된다. - 기존 요격 미사일로 타격 불가능한 경우
새로운 요격 미사일을 추가하고, e 좌표를 x1으로 설정한다.
int x1 = 100000000;
for(int j=0 ; j<targetList.size() ; j++) {
Target t = targetList.get(j);
// 폭격 미사일의 s 좌표가 요격 미사일의 s 좌표보다 크면, 기존 미사일로 타격 가능하다.
if(t.x1>x1) {
x1 = t.x1;
// 폭격 미사일의 e 좌표가 요격 미사일의 s 좌표보다 크면, 기존 미사일로 타격 불가능하다.
} else if(t.x2<=x1) {
x1 = t.x1;
answer++;
}
}
🔑 소스코드
import java.util.*;
public class Solution {
public int solution(int[][] targets) {
ArrayList<Target> targetList = new ArrayList();
int answer = 0;
for(int[] t : targets) {
Target target = new Target(t[0], t[1]);
targetList.add(target);
}
Collections.sort(targetList);
int x1 = 100000000;
for(int j=0 ; j<targetList.size() ; j++) {
Target t = targetList.get(j);
if(t.x1>x1) {
x1 = t.x1;
} else if(t.x2<=x1) {
x1 = t.x1;
answer++;
}
}
return answer;
}
}
class Target implements Comparable<Target> {
int x1;
int x2;
public Target(int x1, int x2) {
this.x1 = x1;
this.x2 = x2;
}
@Override
public int compareTo(Target t) {
if(this.x2==t.x2) return t.x1-this.x1;
else return t.x2-this.x2;
}
}