[Python] 단속카메라

💻 문제 정의

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

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

💡 접근 및 설계

각 차량의 경로 끝 부분을 기준으로 해당 차량이 경로를 나가기 전에 카메라를 만날 수 있도록 카메라를 놓는다고 생각해보자. [-20, -15]의 차량을 잡기 위해 -15지점에 카메라를 설치하면, 이후에 등장하는 차량들 중에서 -15보다 전에서 등장하는 차량도 함께 잡을 수 있다. 만약 시작지점이 -15보다 크다면 해당 차량이 나가는 지점에 카메라를 한 대 더 놓는다.

✏️ 알고리즘 풀이

routes.sort(key=lambda x : x[1])
    
camera = 1
check = routes[0][1]
for start, end in routes:
    if start <= check:
        continue
    
    else:
        check = end
        camera += 1

경로를 각 차량이 고속도로를 나가는 기점을 기준으로 정렬한다. 이후 앞서 설명처럼 카메라를 적절히 배치한다.

🗒️ 최종 제출 코드

def solution(routes):
    routes.sort(key=lambda x : x[1])
    
    camera = 1
    check = routes[0][1]
    for start, end in routes:
        if start <= check:
            continue
        
        else:
            check = end
            camera += 1
    
    return camera

---

💭 오늘의 회고

-