단속 카메라 (python)

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

https://programmers.co.kr/learn/courses/30/lessons/42884
솔루션을 떠올리기 어려웠던 문제, 정렬과 탐욕법을 함께 사용, 그 상황에서 최선의 선택을 하는 문제

👀 깃헙 소스

문제설명

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

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

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

입출력 예

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

솔루션
check에 차량이 카메라를 만났는지 여부를 저장한다.
나가는 지점을 기준으로 routes를 정렬한다
카메라를 만나지 않은 차량이라면 카메라를 차량의 나가는 지점으로 셋팅한다.(최선의 선택) 카메라의 위치가 바뀌었다면 카메라를 만나는 차량의 check를 True로 바꿔준다.

코드

# 파이썬
def solution(routes):

    ENTER, EXIT, N = 0, 1, len(routes)
    routes = sorted(routes, key = lambda x:x[1])
    check = [False] * N
    camera, count = -30000, 0
    for i in range(N):
        if check[i]:
            continue
        count +=1
        camera = routes[i][EXIT]
        for i in range(i, N):
            if routes[i][ENTER] <= camera and camera <= routes[i][EXIT]:
                check[i] = True
    return count