알고리즘(C++) / 프로그래머스 level 3 : 단속카메라

level 3 : 단속카메라

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

코딩테스트 연습 - 단속카메라

 

코드

//프로그래머스 단속카메라
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

    sort(routes.begin(), routes.end()); //빨리 들어가는 순으로 정렬

    int temp = 30001;
    for (int i = 0; i < routes.size(); i++) {
        // 카메라 이동
        if (temp > routes[i][1]) {
            temp = routes[i][1];
        }
        if (routes[i][0] > temp) {
            temp = routes[i][1]; //새로운 카메라 위치
            answer++; //카메라 설치
        }
    }

    return answer;
}

int main() {
    vector<vector<int>> routes = { {-20,15}, {-14,-5}, {-18,-13}, {-5, -3} };
    cout << solution(routes) << "\n";
    return 0; 
}

 

설명

참고 - https://yabmoons.tistory.com/520

[ 프로그래머스 단속카메라 (Lv3) ] (C++)

• routes를 진입한 지점이 빠른 순으로 정렬한다.
• temp의 처음은 하늘색 1에 위치한다.
• 다음 들어온 route의 끝이 temp보다 작으므로 카메라의 위치를 route의 끝으로 옮긴다.
• 다음 들어온 route([-5, -3])의 시작과 끝이 모두 temp보다 크기 때문에 새로운 카메라를 설치해야 한다.

 

고찰

이번 문제는 한참 고민하다가 문제가 풀리지 않아서 구글링 하여 답을 찾을 수 있었다.

코드가 너무 짧아서 당황했다... queue로 풀어야 하나.. 하면서 엄청 복잡하게 생각했는데 코드는 오히려 간단했다. 하지만 코드를 보고서도 왜 이렇게 풀리는지 한참 고민했다. 잘 설명되어있는 블로그를 보니까 이해됐다.

이런 문제는 어떻게 하면 해답을 빨리 찾을 수 있을지 모르겠다... 혼자서는 절대 못 풀었을 거 같다...