[프로그래머스 Level 3] [그리디] 단속카메라 (C++)

안녕하세요! 코딩하는 경제학도 쏘코입니다.

오늘은 그리디의 마지막 문제인 단속카메라를 들고 왔습니다.

이번 문제 역시 아이디어만 잘 떠올린다면 구현은 크게 어렵지 않은 문제였습니다.

바로 살펴보시죠!

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/42884

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

[[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2

programmers.co.kr

0. 문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

0.0. 제한사항

차량의 대수는 1대 이상 10,000대 이하입니다.
routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

0.1. 입출력 예

routes	return
[[-20,15], [-14,-5], [-18,-13], [-5,-3]]	2

0.2. 입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

1. 풀이 과정

정말 간단합니다. 생각해 내기가 어려울 뿐..

처음에는 for문을 무지막지하게 돌려서 중복되는 부분이 있으면 그 부분을 체크하고 또 다음 차랑 비교해서 중복되는 부분이 있으면 그 부분만 남기고 없다면 새롭게 체크하고..를 반복하려고 했더니 코드가 너무나도 지저분해지고 복잡해졌습니다. 구현하다가 이건 아니다 싶어서 다 지워버렸습니다.

해답은 정렬이었습니다. 진출 순서대로 정렬을 한 뒤 카메라에 찍히지 않았다면 진출 지점에 새롭게 카메라를 설치합니다. 이것만 반복해도 끝입니다. 하나하나 자세히 살펴보겠습니다.

먼저 sort와 새롭게 만든 comp 함수를 이용해서 진출 순서대로 정렬합니다.

그 후 진출할 때까지 카메라에 찍히지 않은 경우 진출 지점에 카메라를 설치합니다.

저는 가장 뒤에 위치한 카메라의 위치를 담은 변수인 camera를 하나 만들었습니다.

for문을 이용해서 다음 route의 출발점이 카메라보다 뒤에 있는지를 확인했습니다.

카메라에 찍히지 않았다면(route의 출발점이 카메라보다 뒤에 있다면) answer에 1을 더하고 그 routes의 맨 끝을 새롭게 카메라 설치 위치로 담았습니다. 찍혔다면 그냥 그대로 넘어가면 되겠죠!

2. 소스 코드

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

using namespace std;

// 진출 순서대로 정렬하기 위한 bool함수
bool comp(vector<int>& a, vector<int>& b){
    return a[1] < b[1];
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    // 0. 먼저 빨리 진출하는 순서대로 정렬한다. 그럼 지나갈 때 찍힐테니까!
    sort(routes.begin(), routes.end(), comp);
    // 1. 진출할 때까지 카메라에 찍히지 않은 경우 진출지점에 카메라를 설치한다.
    int camera = -30001; // 카메라가 설치된 위치를 담은 변수 / 초기값은 -30000보다 작아야한다!
    for (int i = 0; i < routes.size(); ++i){
        if(routes[i][0] > camera){ // 카메라 설치 위치가 진입 위치보다 앞이라면
            camera = routes[i][1]; // 새로운 routes 진출구간에 카메라 추가 설치
            ++answer; // 카메라 설치했으니 answer에 1 더함
        }
    }
    return answer;
}