프로그래머스 - 요격 시스템

문제

https://school.programmers.co.kr/learn/courses/30/lessons/181188?language=cpp 

프로그래머스

그리디 문제로 정렬 후 그때그때 최선의 선택을 해서 답을 도출하는 문제였다.

 

문제 풀이

처음에는 target을 정렬한 다음 section vector를 만들어 겹치는 구간을 만들고 각 target 마다 구간 내 가장 겹치는 곳이 많은 곳을 미사일을 쏘는 곳으로 정한 후 section vector에서 --를 해주려고 했었는데 문제 조건에서 target 길이와 s,e 길이가 각각 50만과 1억이어서 아! 이렇게 푸는거 아니구나!라고 생각했다.

 

그리디로 풀어야할 것 같기는 한데 감이 안잡혀서 다른 사람의 코드를 참고했고.. 보자마자 이 방법을 대체 왜 생각 못한건지 의문이 들었다. 그래도 이 문제를 풀어봤기 때문에 다음에 비슷한 유형의 문제를 보면 수월하게 접근할 수 있을 것 같다. 더 연습하자~

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

using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    int i;
    sort(targets.begin(), targets.end());

    int now;
    now = targets[0][1];
    
    for(i=1;i<targets.size();i++){ //하나씩 비교
        if(now <= targets[i][0]){ //다음 타겟과 같이 없애지 못하는 경우
            answer++;
            now = targets[i][1];
        }
        else{
            now = min(now, targets[i][1]);
        }
    }

    return answer+1;
}