[Programmers] 요격 시스템

프로그래머스

 

1. 구현 아이디어 1 - 정답입니다!

입출력 예 설명에 나온 사진을 보고 백준 회의실 배정 문제가 떠올랐다.

이번 문제도 접근 방법이 비슷하다.

 

1. 먼저 끝점을 기준으로 배열을 정렬한다.
2. 변수 e를 사용하여 현재 끝점의 위치를 저장한다.
3. targets 배열을 돌면서 시작점과 e를 비교하면서 필요한 미사일의 수를 구한다.
   • 만약 현재 구간의 시작점이 e보다 크거나 같다면, 미사일이 하나 더 필요하단 뜻이므로 answer을 1 더한다.
   • 끝점을 현재 구간의 끝점으로 갱신한다.

3-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;
}