[프로그래머스 문제풀이] 30. 단속카메라

나의 풀이

문제를 풀고 테스트케이스를 30개 정도 구해서 전부 정답을 맞췄지만 프로그래머스에서는 맞은게 하나도 없다고 나온다...
이러다간 시간만 낭비할 것 같아서 일단 답을 봤는데 엄청 간단하게 풀어져 있었다.
애초에 문제를 접근하는게 잘못된 것 같다.

🎉완성코드

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

using namespace std;

int solution(vector<vector<int>> routes) {
	sort(routes.begin(), routes.end(), [](vector<int> a, vector<int> b) {
		if (a[0] == b[0])
			return a[1] < b[1];
		return  a[0] < b[0];
		});

	int camera_cnt = 0;
	int overlap_cnt = 0;
	bool has_cam = false;
	for (size_t i = 0; i < routes.size(); i++)
	{
		i += overlap_cnt;
		overlap_cnt = 0;

		if (i == routes.size() - 1)
			return ++camera_cnt;

		int tmp = routes[i][1];
		for (size_t j = i + 1; ; j++)
		{
			if (tmp >= routes[j][0])
			{
				if (tmp > routes[j][1])
				{
					++camera_cnt;
					++overlap_cnt;
					has_cam = true;
					tmp = routes[j][1];
				}
				else
				{
					++overlap_cnt;
				}
			}
			else
			{
				if(!has_cam) ++camera_cnt;
				has_cam = false;
				break;
			}

			if (j == routes.size() - 1)
			{
				if (!has_cam) ++camera_cnt;
				return camera_cnt;
			}
		}
	}
}

추천을 많이 받은 풀이

차량의 진입 지점으로 limit와 크기 비교를 하고
차량의 진출 지점을 limit에 대입한다.
진입 지점과 진출 지점의 비교만으로 답을 구할 수 있다.

#include <bits/stdc++.h>

using namespace std;

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

int solution(vector<vector<int>> routes) {
    int answer = 0;
    int limit = -30001;
    sort(routes.begin(), routes.end(), cmp);
    for(int i = 0; i < routes.size(); i++){
        if(limit < routes[i][0]){
            answer++;
            limit = routes[i][1];
        }
    }
    return answer;
}

단속카메라 문제 링크