[Programmers] 단속카메라
문제 설명
문제 설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 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 # Sorting
풀이 과정
출제 빈도가 높지는 않은 그리디 알고리즘 유형의 문제로, 출제 빈도가 낮은 만큼 그 정답률도 낮은 편에 속합니다.
그리디 알고리즘은 보통 정렬을 많이 활용하며, 앞에서부터 차례로 탐색하면서 조건에 맞는지를 확인하며 답을 찾습니다. ‘‘뒤의 상황과 상관없이 앞의(또는 일부분의) 최적값이 전체의 최적값이다’라는 그리디 알고리즘의 일반적인 설명은 저에게 크게 와닿지가 않습니다…ㅎㅎ
이 또한 제가 아직 부족한 탓이겠죠.
어쨌든, 이 문제는 아이디어가 떠오르면 바로 풀리고, 떠오르지 않으면 오래 헤매는 문제입니다.
첫 번째 카메라는 첫 번째로 차가 빠져나가는 지점에 설치해야 합니다. 왜냐하면 이 지점에서 설치하지 않으면 첫 번째로 빠져나가는 차는 찍을 수 없기 때문입니다. 그 지점에 카메라를 설치하면 해당 지점을 지나는 차들은 모두 카메라에 찍히게 되므로 더 이상 신경 쓸 필요가 없습니다.
두 번째 카메라는 아직 카메라에 찍히지 않은 차 중에서 첫 번째로 차가 빠져나가는 지점에 설치하면 됩니다. 두 번째 지점에 카메라를 설치하면 해당 지점을 지나는 차량들은 모두 찍히게 되므로 더 이상 신경 쓸 필요가 없습니다.
이런 식으로 계속 해서 카메라를 설치하는 과정을 거치면 됩니다.
위 과정은 정렬을 통해 쉽게 구현할 수 있습니다. 첫번째로 차의 진출 시점이 빠른 순(오름차순)으로 정렬하고, 진출 시점이 같은 경우를 대비하여 두번째로 진입 시점이 빠른 순(오른차순)으로 정렬합니다.
그리고 앞에서부터 차례로 탐색하며, camera_spot < 다음 route의 진입 시점이 되면 camera_spot을 다음 route의 진출 시점으로 변경하고 cnt+1을 해줍니다.
위 방법만 이해한다면 일반적인 정렬로도 풀 수 있으며, 저는 힙을 활용해 구현해봤습니다.
전체 코드
힙을 활용한 정렬 코드입니다.
def solution(routes):
# 나가는 시간이 빠른순(작은순)으로 정렬, 들어오는 시간이 빠른순(작은순)으로 정렬
# 힙에서 하나씩 빼다가 '기준값의 진출값 < 다음값의 진입값'이 되면 기준값을 다음값으로 바꾸고 cnt+1
import heapq
routes = [(x[1],x[0]) for x in routes] # 힙정렬을 위해 [진출,진입]으로 순서 변경
heapq.heapify(routes)
camera_spot = routes[0][0]
ans = 0
while routes:
route = heapq.heappop(routes)
if camera_spot < route[1]:
camera_spot = route[0]
ans += 1
return ans+1
Leave a comment