[프로그래머스] 단속카메라

문제 출처: 프로그래머스 (https://school.programmers.co.kr/learn/courses/30/lessons/42884#)

 

문제 설명

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

처음 문제를 접했을 때는 완전탐색인가?라고 생각했었다. (아마 DP문제를 계속 풀다와서 그런 것 같다.)

 

첫 시도로 defaultdict로 모든 경로에 대해 방문하는 차량의 대수를 기록하여 문제 풀이를 시도했다.

<틀린코드 보기>

from collections import defaultdict
def solution(routes):
    answer = 0
    routes.sort()
    road = defaultdict(int)
    
    for enter, out in routes:
    	for i in range(enter, out+1):
        	road[i] += 1
    
    start = list(road.keys())[0]
    end = list(road.keys())[-1]
    cur = start
    rec = 0
    
    while cur < end:
    	answer += 1
    	rec = road[cur]
        while rec == road[cur]:
        	cur += 1
            
    return answer

다시 살펴보니 틀린 코드는 여기 올리기 민망할 정도로 논리가 안맞는 수준이었다. 점검을 위해 돌렸을 때 대부분의 케이스에서 시간 초과가 발생하였고, 제대로 돌아간 3개 조차 실패로 나왔다.

 

패착은 이렇다.

1. 방문한 전체 길이의 경로를 탐색하므로 인해 연산이 지나치게 많이 발생하였다.

2. 방문과 탐색을 따로 진행함으로 인해 연산이 두배정도 증가하였다.

3. 해당 도로의 방문 차량 숫자가 달라지는 것과 CCTV 수는 항상 관련이 있는 것은 아니다.

 

나의 잘못된 버릇이 항상 그렇듯 문제를 너무 꼬아 생각하게 되는 것을 하루 빨리 고쳐야 실력 향상에 도움이 될 것 같다..

 

정답은 다음과 같다.

<정답 코드>

from collections import deque
def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[1])
    q = deque(routes)
    
    while q:
        enter, out = q.popleft()
        answer += 1
        while q and q[0][0] <= out:
            q.popleft()

    return answer

이전에 짰던 코드보다 훨씬 간결하게 답안을 작성할 수 있는 것이었다.

 

접근은 아래와 같다.

 

1. 주어진 route에 대해, 먼저 나가는 차량들을 기준으로 정렬한다. 

2. 정렬된 리스트를 queue형식으로 변경한다.

3. queue에서 차량경로를 하나씩 꺼낸 후, 해당 경로 상 임의의 위치에 CCTV 하나를 배치한다 가정하고, 해당 경로 안에서 출발을 하는 차량들을 모두 pop해준다.

 

처음엔 나가는 차량을 기준으로 정렬을 하는게 아닌, 출입하는 차량을 기준으로 정렬을 해야한다고 생각했다.

 

이와 같이 생각한 이유는, 먼저 출발한 차량이 탈출하기 전에 있었던 모든 차량들을 pop해야한다고 생각했기 때문이다.

 

하지만 이런 접근이 틀린 이유는 가장 먼저 출발한 차량이 가장 나중에 탈출하는 경우가 있다면, CCTV 대수는 1대로 출력되기 때문이다. (그리고 가장 먼저 탈출하는 차량을 기준으로 정렬해야한다는 사실을 3시간 만에 떠올렸다...)

 

그리디 문제를 풀 때 가끔씩 드는 생각이지만 해당 코드가 항상 정답을 배출하는 코드일까?라는 의문이 아직까지 남아있지만, 그렇다할 반례를 아직 못찾았다. 반례를 찾게 된다면 추가로 업로드 해야겠다.