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

프로그래머스 - 단속카메라

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

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

제한사항

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

입출력 예

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

return
2

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

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

나의 풀이
문제를 읽다보면 어떻게 접근을 해야할지 보인다.
모든 차량 에서 신장 트리에 대한 힌트를 얻을 수 있으며, 단속용 카메라를 한 번은 만나도록 에서 프림 알고리즘에 대한 힌트를 얻을 수 있다.

왜 프림 알고리즘일까?
프림 알고리즘은 최소 비용 신장 트리(이 문제에서는 카메라 개수가 최소가 되도록)를 구성하는 알고리즘이며, 각 노드를 한번 이상 지날 수 있다.
즉, 모든 차량이 한 번은 단속용 카메라를 만나도록 은 프림 알고리즘을 활용한 문제임을 알려주는 셈이다.

내 풀이가 물론 정석적인 풀이는 아니겠지만 그래도 생각한 대로 잘 풀려서 설명해보기로 함

def solution(routes):
    routes = sorted(routes, key = lambda x:x[0]) # 진입 지점 순으로 정렬
    answer = 1
    a = [routes[0]] # 첫번째 차량은 포함하고 시작
    
    for i in range(1, len(routes)):
        if (routes[i][0] <= a[answer-1][1]): # 공통범위가 존재하면
            a[answer-1] = [routes[i][0], min(a[answer-1][1], routes[i][1])]
        else: # 공통범위가 존재하지 않는다면
            answer += 1
            a.append(routes[i])
    return answer

• 먼저 각 route들을 진입 지점 순으로 정렬한다. 이렇게 함으로써 다음 route 와 공통 범위(인접 노드) 여부를 쉽게 판단할 수 있다.
• 시작 지점으로서 첫번째 route는 범위 집합에 포함하고 카메라의 개수는 1부터 시작한다.
• for 문 : 두번째 route부터 이전 범위와 공통범위가 있는지 판단해서 공통범위가 존재한다면 그 범위를 좁히고, 공통범위가 존재하지 않으면 카메라의 개수를 늘리고 범위 집합에 추가한다(MST 집합에 추가)
• if (routes[i][0] <= a[answer-1][1]): : 이미 오름차순 정렬이 되어 있으므로 이전 범위와 겹치는지만 판단하면 된다.

정렬 후 routes
-20, 15
-18, -13
-14, -5
-5, -3

첫번째 route는 포함했으므로
현재 범위 = [[-20, 15]]

for문 진입시 이미 진입지점은 오름차순으로 정렬되어있으므로
진출지점만 판단하면 된다.
i = 1
[-20, 15]와 [-18, -13]은 공통범위가 존재한다.
카메라 개수 = 1
현재 범위 = [[-18, -13]]

i = 2
[-18, -13]와 [-14, -5]은 공통범위가 존재한다.
카메라 개수 = 1
현재 범위 = [[-14, -13]]

i = 3
[-14, -13]와 [-5, -3]은 공통범위가 존재하지 않는다.
카메라 개수 = 2
현재 범위 = [[-14, -13], [-5, -3]]

수직선 상으로 그림을 그리면서 풀면 좀 더 이해가 쉽다.

그동안 프로그래머스 3단계 문제는 막막했었는데 알고리즘 공부와 같이 꾸준히 문제를 풀다보니 이제 문제가 슬슬 보이기 시작한다!