접근
이 문제는
1. 정렬을 통한 Greedy와
2. 구현의
문제입니다.
- 첫번째 정렬은
막대기의 마지막을 오름차순으로, 마지막 위치가 같은 경우 시작위치를 오름차순으로 정렬하였습니다.
위와 같이 진행하는 이유는 막대기의 마지막위치보다 다른 막대기의 시작위치가 작은 경우 요격으로 같이 격파될 수 있습니다. 그래서 위와 같이 정렬합니다.
- 두번째 구현은 저는 4번의 시도 끝에 맞았습니다.
-
처음 시도: 이분탐색
완전 잘못 접근했습니다.
이분탐색을 통해 현재 막대기의 마지막보다 큰 막대기의 시작위치가 있는지 없는지를 반환하는 내부 메서드를 하나 선언했습니다.하지만 이 방법은 이분탐색이었기 때문에 잘못되었습니다.
이분탐색을 통해서 접근한 mid 위치의 막대기가
현재 위치의 요격시스템에 포함되지 않을지도 모릅니다.현재 위치가 아닌 다른 위치의 막대기에 포함될 수도 있습니다.
따라서 이분탐색으로 풀면 안됩니다.
-
두 번째 시도 : 단순한 구현을 통한 2중 for문
보면 현재 위치 막대기의 마지막 위치보다 크거나 같은 다른 막대기의 처음위치가 등장하는 경우 다른 요격으로 격파되므로
answer에 더하기 1을 하고
다음 검사학 막대기의 위치를 저장하고
tag를 통해 다른 종류의 막대기가 발견되었음을 check합니다.
그리고 break를 통해 내부 for문을 벗어납니다.그러나 문제는 노란색 형관펜 부분에서 발생합니다.
끝까지 돌고 없는 경우 사실 모두 같이 격파될 수 있는 것이기 때문에
굳이 i++을 하여 다시 2중 for문을 돌 필요가 없습니다.그냥 다른 종류의 막대기가 발견되지 않은 경우 다 같은 요격으로 격파되므로
끝이 납니다.
-
세 번재 시도 : 시간초과를 해결한 2중 for문
따라와 위와 같이 모두 같은 요격으로 격파되면 break를 통해 더 이상 검사하지 않고 끝을 냅니다.
다른 분의 더 간단한 풀이를 발견하여 첨부하였습니다.
이분탐색을 이용한 실패한 풀이
import java.util.*;
class Solution {
public int solution(int[][] targets) {
int answer = 0;
//A나라에서 B나라 침고
//B나라 대부분의 전략 자원 - 아이기스 군사 기지에 집중 -> 융단폭격
// B나라 요격 시스테메 최소로 사용해서 모든 폭격 미사일 요격
// 폭격 미사일 x축 평행 , 요격 y축 평행 : 걸쳐진 모든 미사실 한번에 요격
// 단 끝지점은 포함될 수 없음
// 요격 미사일 실수도 가능
// 모든 폭격 미사일을 요격하기 위해 필요한 미사실의 수의 최솟값을 return
Comparator<int[]> comp = new Comparator<>(){
public int compare(int[] c1, int[] c2){
if(c1[1]==c2[1]){
return c1[0]-c2[0]; // 1 index에 대한 오름차순
}else
return c1[1]-c2[1];// 0 index에 대한 오름차순
}
};
Arrays.sort(targets,comp);
for(int i=0;i<targets.length;i++){
// 같거나 큰게 존재하는지 확인
if(find(targets[i][1],i+1,targets.length-1,targets)){
answer++;
}
}
return answer;
}
// 이분 탐색으로 진행
static boolean find(int target, int l, int r, int[][] targets){
int mid =0;
boolean tag = false;
while(l<=r){
mid = (l+r)/2;
if(targets[mid][0]>target){
r=mid-1;
return true;
}else{
l=mid+1;
}
}
return tag;
}
}테스트 케이스 9,10에서 시간 초과한 풀이
import java.util.*;
class Solution {
public int solution(int[][] targets) {
int answer = 1;
//A나라에서 B나라 침고
//B나라 대부분의 전략 자원 - 아이기스 군사 기지에 집중 -> 융단폭격
// B나라 요격 시스테메 최소로 사용해서 모든 폭격 미사일 요격
// 폭격 미사일 x축 평행 , 요격 y축 평행 : 걸쳐진 모든 미사실 한번에 요격
// 단 끝지점은 포함될 수 없음
// 요격 미사일 실수도 가능
// 모든 폭격 미사일을 요격하기 위해 필요한 미사실의 수의 최솟값을 return
Comparator<int[]> comp = new Comparator<>(){
public int compare(int[] c1, int[] c2){
if(c1[1]==c2[1]){
return c1[0]-c2[0]; // 1 index에 대한 오름차순
}else
return c1[1]-c2[1];// 0 index에 대한 오름차순
}
};
Arrays.sort(targets,comp);
for(int i=0;i<targets.length-1;){
boolean tag = false;
// 같거나 큰게 존재하는지 확인
for(int j=i+1;j<targets.length;j++){
if(targets[i][1]<=targets[j][0]){
answer++;
i=j;
tag=true;
break;
}
}
if(!tag){
i++;
}
}
return answer;
}
}위 코드를 고쳐 성공한 풀이
다른 사람의 더 간단한 풀이
import java.util.*;
class Solution {
public int solution(int[][] targets) {
int answer = 1;
//A나라에서 B나라 침고
//B나라 대부분의 전략 자원 - 아이기스 군사 기지에 집중 -> 융단폭격
// B나라 요격 시스테메 최소로 사용해서 모든 폭격 미사일 요격
// 폭격 미사일 x축 평행 , 요격 y축 평행 : 걸쳐진 모든 미사실 한번에 요격
// 단 끝지점은 포함될 수 없음
// 요격 미사일 실수도 가능
// 모든 폭격 미사일을 요격하기 위해 필요한 미사실의 수의 최솟값을 return
Comparator<int[]> comp = new Comparator<>(){
public int compare(int[] c1, int[] c2){
if(c1[1]==c2[1]){
return c1[0]-c2[0]; // 1 index에 대한 오름차순
}else
return c1[1]-c2[1];// 0 index에 대한 오름차순
}
};
Arrays.sort(targets,comp);
int end = targets[0][1];
for(int i=0;i<targets.length;i++){
if(end<=targets[i][0]){
answer++;
end=targets[i][1];
}
}
return answer;
}
}