프로그래머스 lv 3. 42884 단속카메라 c++ **다시 풀어볼것**

 

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

 

#include <bits/stdc++.h>

using namespace std;

bool cmp(const vector<int>& a, const vector<int>& b){
    return a[1]<b[1];
}

int solution(vector<vector<int>> routes) {
    int answer = 0;

    sort(routes.begin(),routes.end(),cmp);
    int c= -30'005;
    for(auto& t: routes){
        if(t[0]>c){
            c=t[1];
            answer++;
        }
    }
    return answer;
}

 

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

위에 첨부한 lv 2. 요격시스템과 동일한 문제. 대신 위의 문제는 개구간, 현재의 문제는 폐구간 형태이다. 

 

요격시스템 문제의 경우는 개구간 이었기 때문에 판단을 해줄때 

if(tar[0]>= t){

...

}

 형태처럼 등호 = 가 있었고, 

이 문제의 경우는 폐구간 이었기 때문에 판단을 해줄때

if(t[0]>c){

...

}

처럼 등호를 포함하지 않았다. 

등호의 포함 여부가 중요하므로 개구간인지, 폐구간인지 등은 문제를 처음 읽을때 확일하게 이해하고 넘어가야 할 것이다. 

 

 

결국 이러한 문제들의 핵심은, 

끝나는 지점들을 오름차순으로 정렬한뒤에, 

그걸 기준으로 겹치는이 안겹치는지를 판단해서, 

안겹치는 새로운 것이 나온다면, 미사일을 쏘던, 카메라를 새로 설치하던 하는 식으로 해서 

판단하는 문제이다. 

이 문제의 경우 내 기억에 요격시스템은 정렬부분에서 나왔던것 같고, 

현 문제의 경우는 그리디에서 나왔는데, 

결국 정렬을 이용한 그리디 문제이다. 

위와 같은 형태로 판단하는 것은 결국 그리디적으로 문제의 해결 방법을 결정짓고 코드를 작성한 것이기 때문에

이런 문제의 경우는 그리디 풀이를 생각해내면 된다. 

물론 그리디 문제의 경우 결국 엄밀하게 따지면 수학적으로 증명해내야 하겠지만, 코딩테스트 수준에서는 생략하자.