반응형
1. 구현 아이디어 1 - 정답입니다!
입출력 예 설명에 나온 사진을 보고 백준 회의실 배정 문제가 떠올랐다.
이번 문제도 접근 방법이 비슷하다.
- 먼저 끝점을 기준으로 배열을 정렬한다.
- 변수 e를 사용하여 현재 끝점의 위치를 저장한다.
- targets 배열을 돌면서 시작점과 e를 비교하면서 필요한 미사일의 수를 구한다.
- 만약 현재 구간의 시작점이 e보다 크거나 같다면, 미사일이 하나 더 필요하단 뜻이므로 answer을 1 더한다.
- 끝점을 현재 구간의 끝점으로 갱신한다.
2. 전체 코드
#include <vector>
#include <algorithm>
using namespace std;
// 끝점을 기준으로 정렬하기 위해 사용자 정의 함수 구현
bool comp(vector<int> a, vector<int> b) {
if (a[1] < b[1]) return true;
return false;
}
int solution(vector<vector<int>> targets) {
int answer = 0;
sort(targets.begin(), targets.end(), comp);
int e = 0;
for (auto target : targets) {
if (target[0] >= e) {
answer ++;
e = target[1];
}
}
return answer;
}
반응형