[알고리즘C++]단속카메라

오늘의 문제

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

단속카메라

나의 풀이

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

using namespace std;

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

모범 답안

#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;
}

배울 점

• 처음에 2차원 벡터를 사용했다가 메모리 초과가 났었다.
• sort를 이용하면 앞뒤를 같이 비교할 필요가 없어지는점을 이용하여 quick sort기반의 sort함수를 사용했다.
• 프로그래머스의 레벨시스템은 이상하다..