고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한 조건
입출력 예시
핵심: 카메라를 어디 위치에 둘 것인가?
→ 차량의 경로 구간이 많이 겹치는 지점에 카메라를 설치하자
3가지의 경우의 수
겹치는 부분이 전혀 없을 경우: 아무 곳이나 설치
한 경로가 다른 경로를 완전히 포함할 경우: 경로가 더 짧은 쪽의 진출 지점
완전히 포함하지는 않으나 겹치는 구간이 존재할 경우: 겹치는 구간 쪽의 진출 지점
✅ 3가지의 경우를 모두 만족시키는 위치는 경로의 진출지점이다. → 카메라 위치는 진출지점이 적당
[[-20, -15], [-18, -13], [-14, -5], [-5, -3]]
def solution(routes):
answer = 0 # answer: 필요한 카메라 개수
# 진출이 낮은 순으로 정렬
routes.sort(key = lambda x: (x[1], x[0]))
camera = -30001 # 최소 카메라 위치 지점
for r0, r1 in routes:
if camera < r0:
answer += 1
camera = r1 # 가장 최근 카메라의 위치를 갱신
else: # camera >= r0
pass
return answer