Programmers - 단속카메라

문제 링크

처음에 떠올린 것은 모든 지점에 대해 차가 가장 많은 지점을 하나씩 찾으면서 제거하는 완전탐색 방식이었다.
하지만 지점이 60000개이고 차가 최대 10000개 라서 지점을 하나 찾는데만 60000*10000 번의 연산이 필요하기 때문에 완전탐색으로는 해결이 불가능하다는 것을 알았다.

따라서 문제 분류대로 그리디 하게 접근해야 하는데 어떻게 할지를 떠올리지 못해서 질문하기에 있는 풀이를 보고 이해했다.

1. 나가는 순서대로 정렬
2. 첫번째 차의 범위 이내에 무조건 카메라가 있어야 함
   -> 첫번째 차의 나가는 지점에 카메라를 놓는 것이 가장 유리함.
   (최대한 다른 차들이 겹치게)
3. 찍힌 차를 제거해가면서 안찍힌 차가 없을 때 까지 반복
4. 2~3 을 반복한 횟수를 return

나가는 순서대로 정렬하고, 첫번째 차가 나가기 전에 무조건 카메라가 있어야 한다고 생각하는 방식이 신기했다.

def solution(routes):

    routes.sort(key=lambda x: x[1])

    cameras = 0
    while len(routes) > 0:
        point = routes[0][1]
        routes = list(filter(lambda x: not x[0] <= point <= x[1], routes))
        cameras += 1

    return cameras