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

 

문제

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

프로그래머스

문제 설명

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

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

풀이

그리디 문제다. 그리디는 따로 정석 구현이 있는 알고리즘이 아니라 일종의 컨셉이지만, 배열 + 그리디면 잘 알다시피 정렬이 중요한 경우가 많다.

단순하게 생각해보자, 문제에서 주어지는 것은 시작 위치와 종료 위치다. 그냥 종료하는 위치를 기준으로 오름차순 정렬한 후에 앞에서부터 탐색을 한다.

현재 자동차의 종료 위치에 카메라를 설치하고, 다음 자동차를 살펴본다. 다음 자동차의 시작 위치가 이전 자동차의 종료 위치(즉 카메라가 설치된 위치)보다 앞에 있으면 다음 자동차도 설치된 카메라를 만나게 된다. 그렇지 않다면 또 그 자동차의 종료 위치에 카메라를 설치하면 된다.

그러면 알고리즘은 다음과 같이 세울수 있다.

1. 카메라 설치 위치를 -30001 로 초기화한다.
2. routes를 차량 진출 위치 기준으로 오름차순 정렬한다.
3. 순서대로 차량을 탐색한다.
   1. 시작 위치가 현재 카메라 설치 위치보다 크다면 이 차량은 카메라를 만나지 못하므로 종료 위치에 카메라를 설치한다.
   2. 시작 위치가 현재 카메라 설치 위치보다 작다면 1번에서 한 정렬 때문에 카메라를 무조건 만나게 된다. 그러므로 패스한다.
4. 카메라 설치 개수를 리턴한다.

코드

def solution(routes):
    answer = 0
    routes.sort(key = lambda x: x[1])
    currentCamera = -30001
    for route in routes:
        if route[0] > currentCamera:
            answer += 1
            currentCamera = route[1]
    
    return answer