[Programmers] 단속 카메라

안녕하세요. 이번 포스팅에서는 Programmers 단속 카메라 문제를 풀어보도록 하겠습니다.

 

해당 문제는

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

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

 

위 링크에서 확인하실 수 있습니다.

 

대표적인 그리디 구간 문제입니다. 보통 이런 문제는 시작점을 기준으로 정렬 or 끝점을 기준으로 정렬하면 풀이의 실마리를 얻을 수 있습니다.

 

저는 이 문제를 끝점을 기준으로 정렬한 뒤,

벡터를 탐색하면서 마지막으로 저장된 끝점보다 현재 검사하는 구간의 시작점이 뒤인 경우 끝점을 바꾸어 주고, 결괏값을 추가해주었습니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 1;
    vector<pair<int,int>> v;
    for(int i = 0; i < routes.size(); i++) v.push_back({routes[i][1], routes[i][0]});

    sort(v.begin(), v.end());
    int pt = v[0].first;
    for(int i = 1; i < v.size(); i++) {
        if(v[i].second > pt) { answer++, pt = v[i].first; };        
    }
    return answer;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.