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

문제 풀러가기

코드 보기

def solution(routes):
 answer = 0
 
 # 차량 진출 기준 정렬
 routes = sorted([[x[1], x[0]] for x in routes])
 
 while routes: # 모든 차량이 단속에 걸릴 때까지
     deleted = []
     [deleted.append(route) for route in routes if route[1] <= routes[0][0]] # 단속에 걸리는 모든 차량 체크
     [routes.remove(delete) for delete in deleted] # 단속에 걸린 차량 제외
     answer += 1 # 한번의 단속으로 가능한 최대 단속
 
 return answer

문제 설명

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

고속도로를 이동하는 차량의 경로 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

입출력 예 설명

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

설명 & 구현 방법

해당 문제는 탐욕(Greedy) 알고리즘으로 쉽게 풀 수 있었다.
사실 Greedy 알고리즘을 구현하는 것은 쉽지만, 그냥 문제만 보았을 때, 해당 문제가 Greedy 인지 파악하는 능력이 더 중요한 것 같다.
프로그래머스에서는 문제 풀기 전 Greedy 알고리즘이라는 언질이 있었기 때문에 더욱 쉽게 풀었던 것 같다.

해당 문제의 키포인트는 어떤 시간이 가장 많은 차량을 단속할 수 있는 시간인가?이다.
가장 단속이 많은 시간대의 차량을 제외한 뒤 남은 차량들을 기준으로 또, 가장 많은 단속 시간대를 구하다 보면, 최소한의 단속 회수가 나오게 된다.
구현적으로 생각하면, 차량의 진출 시간으로 기준으로 정렬이 되어있을 때, 가장 빠른 차량 진출시간을 기준으로 해당 시간에 다른 차량이 포함되는 지만 체크하면된다.

1 ----
2   ------
3  ----------
4        ---------

1. 위와 같이 진입 진출이 정렬되어 있다고 가정했을 때, 1번 차량이 포함되는 시간 중 가장 늦은 시간은 진출 시간이고, 진입 시간이 해당 진출 시간 안에 있는 모든 차량(1, 2, 3)은 단속에 걸리는 차량이다.
   왜냐하면, 진출 시간을 기준으로 정렬했기 때문에 비교하려는 진입 시간이 기준이 되는 진출 시간보다 앞에 있다면 무조건 포함관계이기 때문이다.
2. 단속에 걸리는 차량은 제외한 뒤, 다시 1번을 반복한다.
3. 단속에 걸리지 않은 차량이 없을 때까지 반복한 뒤, 반복한 회수를 반환하면 된다.