Programmers - 단속카메라

---

title: Programmers - 단속카메라
date: 2022-08-12
tags:

• Algorithm

---

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

문제 요약

차량이 고속도로에 진입한 지점, 그리고 탈출한 지점이 vector로 넘어온다.
모든 차량을 단속할 수 있도록 카메라를 설치할 때, 최소 설치 대수를 return한다.

문제 풀이

앞, 혹은 뒤를 기준으로 greedy하게 접근하였다.
앞(-)에서 접근한다면 탈출 지점이 가장 작은 값을 찾은 뒤, 이를 기준으로 해당 범위에 포함되지 않는 차량에 대해 다시 앞의 내용을 반복한다.
뒤(+)에서 접근한다면 반대로 진입 지점이 가장 작은 값을 기준으로 하면 된다.


vector를 이용한다면 중간에 원소를 제거해야 하는데, vector는 중간 원소의 삭제할 때 overhead가 크다.
지금 생각하면 이 풀이를 사용하면 List가 더 적절한데, 익숙한 queue가 떠올라 queue를 사용하였다.
차량 후보들을 확인하며 탈출 지점이 가장 작은 값을 갱신해주며 queue에 넣는다.
이후 해당 queue에서 하나씩 꺼내며, 설치할 위치에 포함되지 않으면 다른 queue에 집어넣으며 이 때의 탈출 지점이 가장 작은 값을 따로 갱신해준다.
두 queue가 번갈아 쓰이기에 포인터를 이용하여 처리한다.


이 방식도 성능이 괜찮긴 하나, 다른 유저들이 푼 풀이 중 훨씬 좋은 풀이가 존재한다.
탈출 지점을 기준으로 오름차순으로 정렬한 뒤, 가장 작은 값부터 탐색을 시작한다.
현재의 값보다 탐색하는 진입 지점이 더 클 경우, 이 지점의 탈출 지점으로 값을 갱신해주고 설치 대수를 1대씩 증가시킨다.
탈출 지점을 기준으로 정렬하여 처음부터 탐색하였기에 탈출 지점은 더 왼쪽에 존재할 수 없다. 그렇기에 진입 지점이 더 클 경우, 새로 설치 구간을 갱신해주는 것이다.
설치 구간을 갱신하는 과정에서 새로운 구간보다 더 좌측에서 탈출하는 차량은 없고, 갱신할 구간의 끝 위치인 탈출 지점에서 새로 설치하기에 이것이 best가 되는 것이다.

프로그램

#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using std :: vector ;
using std :: queue ;
using std :: pair ;
using std :: make_pair ;
using std :: min ;

int solution ( vector < vector < int > > routes )
{
    int answer = 0 ;
    queue < pair < int , int > > q1 ;
    queue < pair < int , int > > q2 ;
    queue < pair < int , int > > * qpCurrent = & q1 ;
    queue < pair < int , int > > * qpNext = & q2 ;
    int iCurrentMinEnd = 30000 ;
    int iNextMinEnd ;
    int iRouteSize = routes.size () ;



    for ( int i = 0 ; i < iRouteSize ; ++i )
    {
        int * ipTemp = routes [ i ].data () ;

        ( * qpCurrent ).emplace ( make_pair ( ipTemp [ 0 ] , ipTemp [ 1 ] ) ) ;
        iCurrentMinEnd = min ( iCurrentMinEnd , ipTemp [ 1 ] ) ;
    }
    while ( ! ( * qpCurrent ).empty () )
    {
        iNextMinEnd = 30000 ;

        while ( ! ( * qpCurrent ).empty () )
        {
            pair < int , int > pTemp = ( * qpCurrent ).front () ;
            ( * qpCurrent ).pop () ;

            if ( ( iCurrentMinEnd < pTemp.first ) || ( pTemp.second < iCurrentMinEnd ) )
            {
                ( * qpNext ).emplace ( pTemp ) ;
                iNextMinEnd = min ( iNextMinEnd , pTemp.second ) ;
            }
        }

        ++ answer ;
        if ( q1.empty () )        // Set qpCurrent : q2 , qpNext : q1
        {
            qpCurrent = & q2 ;
            qpNext = & q1 ;
        }
        else                    // Set qpCurrent : q2 , qpNext : q1
        {
            qpCurrent = & q1 ;
            qpNext = & q2 ;
        }

        iCurrentMinEnd = iNextMinEnd ;
    }


    return answer ;
}