Programmers - 단속카메라[파이썬(python)]

문제 출처 : 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

 

입출력 예 설명

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

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

---

문제 풀이

greedy 알고리즘으로 풀 수 있는 문제이다.

이 문제는 routes의 원소를 진입 지점을 기준으로 정렬하고, 순차적으로 routes의 [진입 지점, 진출 지점]을 순회하면서 세 가지 의사 결정을 수행하면 된다. 의사 결정의 세 가지 종류는 아래와 같다.

• 새로 단속 카메라를 추가하는 방법밖에 없으므로 단속 카메라를 하나 추가한다.
• 기존에 설치되어 있던 단속 카메라의 위치를 옮긴다.
• 기존에 설치되어 있던 단속 카메라를 그자리 그대로 둔다.

위의 세가지 의사결정을 수행하는 기준은 아래와 같다.

 

1. 새로 단속 카메라를 추가하는 방법밖에 없으므로 단속 카메라를 하나 추가하는 경우

• 새로 들어온 차량의 진입 지점이 단속 카메라의 위치보다 앞에 있는 경우 새로 단속 카메라 하나를 추가한다. 이때 단속 카메라가 추가되는 위치는 새로 들어온 차량의 진출 지점이 된다.
• routes 배열은 진입 지점을 기준으로 정렬되어있기 때문에 이후에 새로 차량이 들어왔을 경우에 단속 카메라의 위치는 이전 차량의 진출 지점에 설치되어 있으므로 새로 들어온 차량의 진입 지점이 단속 카메라의 위치보다 앞에 있는 경우 새로 단속 카메라를 추가하여야 한다.

2. 기존에 설치되어 있던 단속 카메라의 위치를 옮긴다.

• 새로 들어온 차량의 진입 지점과 진출 지점이 모두 카메라 설치 위치보다 작은 경우 routes 배열이 진입 시점을 기준으로 정렬되어있으므로 이경우 카메라를 새로 들어온 차량의 진출 지점으로 옮겨준다면 이전 차량과 새로 들어온 차량이 모두 카메라를 마주치도록 배치가 가능하다.

3. 단속 카메라를 그 자리 그대로 둔다.

• 새로 진입한 차량의 진입 지점이 카메라 설치 지점과 같거나, 진입 지점이 카메라 설치 지점보다 작고, 진출 지점 카메라 설치 지점보다 큰 경우 카메라를 옮기거나 추가할 필요가 없으므로 아무것도 하지 않고 계속해서 다음 차량을 순회한다. 

주저리주저리 설명했지만 직접 3가지 경우를 종이에 그려보면 쉽게 이해할 수 있을 것이라 생각한다.

구현 코드

코드 링크 : 단속카메라

def solution(routes):
    routes.sort()
    cam = -30000
    count = 0
    for start, end in routes:
        if start > cam:
            count += 1
            cam = end
        elif start < cam and end < cam:
            cam = end
        else:
            continue
    return count