[C++] 프로그래머스 | 요격 시스템

기분 낼 겸 오랜만에 프로그래머스.. 풀어봤다.

카카오 테크 캠퍼스 붙고나서 온전히 개발에만 몰두했기에....... 거의 5개월만인듯 하다..

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

간단히 그리디하게 풀 수 있는 문제다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool compare(vector<int> &a, vector<int> &b) {
    if(a[0] != b[0]) {
        return a[0] < b[0];
    } else {
        return a[1] < b[1];
    }
}
int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(), targets.end(), compare);

    for(int i = 0; i < targets.size();) {
        int last = targets[i][1];

        while(i < targets.size() && last > targets[i][0]) {
            last = min(targets[i][1], last);
            i++;
        }
        answer++;
    }
    return answer;
}

먼저, 정렬을 해준다.

 

인덱스 i를 이용해서 targets 벡터를 하나씩 확인한다. 현재 미사일의 끝점을 last에 저장한다.

while로 현재 미사일의 끝점 last가 다음 미사일의 시작점보다 크면 계속해서 다음 미사일을 확인한다.

만약 현재 미사일의 끝점이 다음 미사일의 시작점보다 크다면, 두 미사일은 한 번에 요격 가능하다.

그래서 두 미사일 중 끝점이 더 작은 값을 last로 갱신한다. 이렇게 함으로써 현재 요격 가능한 영역에 포함되는 모든 미사일을 한 번에 요격할 수 있는 것이 보장된다. (그리디하게)

 

i를 증가시켜 다음 미사일로 넘어가고, while이 끝나면 answer를 1 증가시킨다.

 

모든 미사일들을 순회하면서 선택된 요격 미사일들의 개수인 answer를 반환한다.

이 값은 모든 폭격 미사일을 요격하기 위해 필요한 최소한의 요격 미사일 수이다..