요격 시스템
요격 시스템 문제는 먼저 sorting을 해주어야 한다.
이 때 어느 값을 기준으로 정렬할 것인지가 관건이 되는데..
주어진 예제에서 어떤 폭격 미사일 하나의 구간만을 고려한다고 해보자.
예를 들면 4-5 구간의 미사일만을 고려해 보자.
4를 요격 범위의 start로 S, 5를 요격 범위의 end로 E라고 표현하고, 현재의 요격 범위로 두자.
end가 4(현재의 S)보다 작은 미사일의 경우, 현재의 요격 범위에 포함될 수 없다.
따라서 start가 5(현재의 E)보다 큰 미사일의 경우에도 현재의 요격 범위에 포함될 수 없다.
그러므로 요격 범위에 들어올 자격이 되는지는, 각 미사일 구간의 end 포인트 지점에 달려있다.
따라서 end를 기준으로 오름차순 정렬해준다.
end를 기준으로 오름차순 정렬해주면
[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4] → [1,4], [4,5], [3,7], [4,8], [5,12], [11,13], [10,14]
이 된다.
미사일을 어차피 한번이상 쏘게 되어 있으니까, count는 1로 시작한다.
처음 요격 구간을 [1,4]로 설정하고 그 다음 구간부터 차례로 순회한다.
첫 S=1, E=4가 된다.
다음 미사일의 범위가 [4,5]이고, 이것의 시작 지점인 4가 현재 요격 구간의 E보다 작아야 한번에 쏠 수 있다.
(엔드 포인트인 4에서는 쏘지 못한다. 조건에 명시되어 있다.)
그런데 E보다 작지 않기 때문에 이 구간에는 첫번째 미사일 구간 빼고는 더이상 요격할 미사일이 없는 것이다.
따라서 count를 1올려주고, 다음 미사일 구간의 시작점을 s로, 끝점을 e로 하여 새로운 요격 범위를 갱신하고 위 과정을 반복하도록 한다.
그럼 최종 요격 발사 횟수를 COUNT를 반환함으로써 얻을 수 있다.
C++로 해결한 코드는 아래와 같다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(vector<int> &v1, vector<int> &v2) {
if (v1[1] == v2[1])
return v1[0] < v2[0];
else return v1[1] < v2[1];
}
int solution(vector<vector<int>> targets) {
int answer = 0;
sort(targets.begin(), targets.end(), cmp);
int e = targets[0][1];
answer++;
for (int i = 1; i < targets.size(); i++) {
if (targets[i][0] < e) {
continue;
}
else {
answer++;
e = targets[i][1];
}
}
return answer;
}
'CO-TE > 프로그래머스' 카테고리의 다른 글
[프로그래머스] MYSQL LV2 조건에 맞는 도서와 저자 리스트 출력하기 / 풀이방법 (1) | 2023.10.17 |
---|---|
[프로그래머스] c++ LV2 택배 배달과 수거하기 (2023 KAKAO BLIND RECRUITMENT) 풀이/접근 방식 (0) | 2023.10.12 |
[프로그래머스] c++ LV1 대충 만든 자판 (0) | 2023.09.13 |
[프로그래머스] c++ LV1 덧칠하기 (1) | 2023.09.13 |
[프로그래머스] c++ LV1 공원 산책 (0) | 2023.09.04 |