[프로그래머스 LV3] - 단속카메라(그리디) c++

문제

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

프로그래머스

접근방법

진출 기준으로 정렬해야하는데,

진입 기준으로 정렬해서, 계속 틀렸다.

 

진입 기준으로 정렬하는 경우, 

중간에 진출이 빠른 케이스가 들어오면(예시 - [[0, 10], [1, 10], [2, 3], [4, 5]])

그것까지 포함해 하나로 처리해버려서 문제가 생긴다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;



int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end(), [](vector<int> a, vector<int> b) {
        return a[1] != b[1] ? a[1] < b[1] : a[0] < b[0];
    });
    int left = -30001;
    for (int i=0;i<routes.size();i++) {
        while (i < routes.size() && routes[i][0] <= left) {
            i++;
        }
        if (i < routes.size()) left = routes[i][1];
        else break;
        answer++;
    }
    return answer;
}

개선할 점