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

문제

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

프로그래머스

풀이

[그리디 + 정렬]

그니까 나는.. 그리디가 매우 약한 것 같다. 이런 논리력 어떻게 갖추나요.. 많이 푸는 게 답이겠지?

글씨는 .. 노답이지만 나름 혼자 이해하려고 열심히 노력했다.

1. 일단 e를 기준으로 오름차순 정렬을 한다. 왜냐면? e를 기준으로 비교를 해야한다! i-1번째 타깃의 e와 i번째 타깃의 s를 비교해야하는데, e를 기준으로 오름차순으로 정렬해야 최소라는 기준을 만족시킬 수 있다.

2. e=0에서 시작, 1~4를 먼저 보면 일단 기존의 e가 새로 들어온 공격의 s인 1보다 작으니까, 해당 공격은 요격을 해야한다. 그리고 e를 업데이트 해준다. 4로 업데이트 해야한다. 다음 공격의 시작이 4보다 작으면, 그건 지금 요격한 걸로 막을 수 있다. 근데 4보다 크거나 같으면 새로 요격을 해줘야한다. 이걸 반복하면 되고, 글로 적어서 설명해뒀다.

C++의 정렬은 확실히 python보다 불편하다.. 익혀두자.. 그리고 python되는 회사 코테면 웬만해선 python으로 푸는게 정신건강에 이로울듯 ..ㅎㅎ

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int cmp(vector<int>& a, vector<int>& b){
    return a[1]<b[1]; //e를 기준으로 정렬
}
int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(), targets.end(), cmp);
    int e =0;
    for(auto t:targets){
        if(e<=t[0]){ //마지막으로 요격한 부분이 감당할 수 있는 범위 e보다 현재 미사일의 시작부분 s가 더 크거나 같으면, 새로운 요격을 해야함.
            answer++;//답 추가하고
            e = t[1]; //감당할수 있는 e를 새로 업데이트 해줌
        }
    }
    return answer;
}