[프로그래머스] 단속카메라 by 파이썬 (Python) : 탐욕법

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

프로그래머스

 

난이도

LV 3

 

 

문제 설명 

고속도로를 이용하는 차량들의 경로 routes가 주어진다.

routes안에는 차량이 고속도로를 진입하는 지점, 나간 지점이 적혀있다.

i 번 째 차량은 routes[i][0]에 고속도로에 들어오고 routes[i][1]에 고속도로에서 나간다.

고속도로를 이용하는 모든 차량이 적어도 한번은 단속 카메라를 만나게 하기 위해서 카메라를 최소 몇대 설치해야하는지 return 한다.

 

 

접근법

가장 최소의 카메라 수를 찾아내야 할 방법은 먼저 들어온 차량이 고속도로를 나갈 때 카메라를 만나게 된다면 최대한 카메라 수를 단축 시킬 수 있다.

고속도로의 차들을 나가는 순서내로 오름 차순 정렬하고 가장 앞의 차량이 고속도로에서 나가는 지점에 우선 카메라를 설치한다.

오름차순 정렬되어있으므로 차량이 나가는 순서대로 정렬되어 있다. 따라서 앞에 저장된 카메라 위치보다 나중에 고속도로에 들어오면 해당 차량이 나갈 때 카메라를 설치해줘야한다.

이런식으로 모든 차량을 검사한후, 카메라의 개수를 return해주면 된다.

 

 

코드

def solution(routes):
    routes.sort(key = lambda x : x[1])
    camara = []
    camara.append(routes[0][1])

    for i in range(1, len(routes)):
        if routes[i][0] > camara[-1]:
            camara.append(routes[i][1])

    return len(camara)

---