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

프로그래머스의 단속카메라(Lv3) 문제이다.

[ 문제풀이 ]

모든 차량이 한번씩은 카메라를 만나도록 하기 위해서 단속 카메라를 최소 몇 개를 설치해야 하는지 구해야 하는 문제이다.

본인은 가장 먼저 차량들의 진입/진출 지점들을 정렬을 시켰다. 더 정확하게 말하면 "차량들의 진입 지점들을 기준으로 오름차순 정렬" 을 시켜 주었다. 그래서 진입 지점이 가장 작은 차량들부터 카메라를 만나게 하기 위해서 설치하는 방식으로 진행하였다.

그럼 진입 지점들을 기준으로 정렬되어 있는 상태라고 가정하고 문제를 풀어보자.

.

예를 들어서 정렬시켰을 때, 진입 지점의 좌표값이 가장 작은 차량(1번 차량)이 저렇게 x ~ y 만큼을 간다고 가정해보자.

그럼 그 다음 들어오는 차량의 진입 지점의 좌표값은 x이상일 것이다. (정렬 시켰으므로)

이 때, 위의 그림에 나온 첫 번째 차량을 카메라에 담기 위해서는 어디에 카메라를 설치하는 것이 가장 이상적일까 ???

1. 진입지점에 설치(x좌표)

2. 진출지점에 설치(y좌표)

3. x ~ y 중간 어디간에 설치

위의 3가지 경우 중에서 어디에 설치하는 것이 이상적일까 ?? 바로 2번인 진출지점(y좌표)에 설치하는 것이 가장 이상적이다.

먼저, 1번 지점 같은 경우는 굉장히 비효율적이라고 생각한다. 왜냐하면 그 다음 차량의 진입 지점은 최소 x좌표 이상인데 1번 차량을 위해서 x좌표에 카메라를 설치하게 되면, 그 다음 차량을 카메라에 못 담을 확률이 굉장히 높아지게 된다.

극단적인 예를 들어보면 다음과 같은 상황이 발생할 확률이 높다는 것이다.

.

1번 차량의 x ~ y가 검은색으로 그려져 있고 , x좌표에 카메라를 설치한다면(빨강색 동그라미) , 2번차량(노랑색 선)을 담을 수가 없다. 반대로 , 위에서 이야기했던 2번 혹은 3번 지점에(파랑색 삼각형) 카메라를 설치한다면 , 1번 2번 차량을 모두 한번에 담을 수 있다는 것이다. 즉 ! 진입지점에 설치하는 것은 굉장히 비효율 적이다.

다음으로, 3번 지점 같은 경우는 굉장히 애매한다고 생각한다. x ~ y 중간 지점의 어딘가에 설치한다고 했는데 그 어딘가의 값을 어떻게 계산할 수 있을까 ? 계산을 할 수 있다면, 결과값들 중에서 어느 좌표가 가장 이상적일까 ?? 알 수가 없다.

따라서, 가장 이상적인 카메라를 설치하는 좌표는 2번(진출지점 : y좌표)에 설치하는 것이다.

.

그럼 이렇게 카메라를 설치했다고 생각해보자. (최소 카메라 1대는 무조건 필요하기 때문에 저렇게 설치했다고 가정)

그럼 2번 차량이 가질 수 있는 가능한 모든 진입/진출 지점에 대한 그림을 그려보면 다음과 같다.

.

이렇게 크게 3가지가 발생할 수 있다. (위의 그림에서 검은색 x ~ y는 1번차량 , 노랑색 nx ~ ny는 2번차량)

1번 Case에서는 기존에 'Y'좌표에 설치해놓은 카메라에 2번 차량을 담지 못한다. 그럼 카메라를 하나 더 추가해주어야 할까 ??

추가해 주지 않아도 된다. 왜냐하면 , 카메라의 위치를 옮기기만 하더라도 2대의 차량을 모두 한번에 다 잡을 수 있는 지점이

존재하기 때문이다.

2대의 차량을 모두 한번에 다 잡을 수 있는 지점은 nx ~ ny 중 어디가로 옮겨주기만 하면 된다.

그럼 첫 번째 카메라를 설치했을 때와 마찬가지로 다음과 같이 카메라를 옮길 수 있는 경우의 수가 발생한다.

1. nx 로 옮기기

2. ny 로 옮기기

3. nx ~ ny 어딘가로 옮기기

위의 3가지 지점 중 어디로 옮기더라도 1번 차량과 2번 차량을 하나의 단속 카메라로 모두 잡을 수가 있다.

그럼 위의 3가지 경우 중 어디가 가장 이상적일까 ?? 첫 번째 단속카메라를 설치했을 때와 같은 이유로 ny에 설치하는 것이

가장 이상적이다.

2번 Case는 카메라를 새로 설치하거나 옮길 필요가 없다. 왜냐하면 이미 하나의 카메라로 2대의 차량을 모두 단속할 수 있기 때문이다.

3번 Case는 카메라를 반드시 하나 새로 설치해 주어야 한다. 어떻게 카메라를 옮기더라도 절대로 하나의 카메라로 2대의 차량을 모두 잡을 수는 없기 때문이다. 그럼 이 때도 똑같은 논리가 적용된다. 카메라를 하나 더 설치해야 되는데 어디에 설치하는 것이

가장 이상적일까 ?? 또 똑같은 이유로 'ny'에 설치하는 것이 가장 이상적이다.

그럼 정리해보자. 간단하게 위에서 표현한 x, y, nx, ny를 이용해서 적어보겠다.

1. ny < y 인 경우, 카메라의 위치를 ny로 옮기기 ! (1번 Case)

2. nx > y 인 경우, 카메라를 반드시 하나 더 설치해주기 ! (3번 Case)

3. nx < y < ny 인 경우, 카메라를 그대로 두면 된다. 따로 해줄 것이 없다 !

위의 내용을 코드로 구현하면 된다. 코드는 간단한 편이고, 주석이 달려있으니 코드에 대한 별도의 설명을 하지 않겠다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<vector<int>> routes) 
{
    int answer = 1;
    sort(routes.begin(), routes.end());
    /* 진입 지점을 기준으로 오름차순 정렬 */
 
    int Cam_Pos = routes[0][1];
    /* 가장 초기의 카메라 좌표는 Y좌표 ! */
 
    for (int i = 1; i < routes.size(); i++)
    {
        if (routes[i][1] < Cam_Pos) Cam_Pos = routes[i][1];
        /* if문은 ny < y 인 경우에 해당하는 상황. */
        /* 카메라를 새로 설치할 필요는 없고, ny로 옮겨주면 된다. */
        else if (routes[i][0] > Cam_Pos)
        {
            answer++;
            Cam_Pos = routes[i][1];
        }
        /* else-if 문은 nx > y 인 경우에 해당하는 상황. */
        /* 카메라를 반드시 새로 설치해야 한다. 설치 지점은 ny.*/
    }
    return answer;
}