[웅's 프로그래머스] 단속카메라 - 파이썬(python) 풀이

이 문제는 처음에 문제를 이해하기 위해 종이에 다음과 같은 좌표(?) 그림을 그려보았다. 

 

문제 자체가 자동차들의 데이터를 바탕으로 카메라 위치를 결정하는 문제이기 때문에 자동차 데이터 들을 먼저 정렬할 필요성을 느꼈다. 자동차의 데이터에 따라서 카메라의 개수를 결정하면 되는 문제라고 생각했다.

 

문제는 정렬의 기준이었다. 자동차들이 들어오는 시간을 기준으로 할 것인지 혹은 나가는 시간을 기준으로 할 것인지 였는데, 나가는 시간을 기준으로 정렬하고자 했다. 

뭐로 하든 상관 없을 것 같은데, 나가는 순으로 정렬하면 다음과 같은 경우의 수를 줄일 수 있었다.

기준으로 선택한 자동차의 나가는 시간과 다음 자동차의 들어오는 시간을 비교해야 하는데 나가는 순으로 정렬되어 있다면 위 경우 처럼 다음 자동차의 나가는 시간이 기준 자동차의 나가는 시간보다 앞서는 경우는 계산하지 않아도 되기 때문이다. 

 

적으면서도 어려운 말을 하고 있는 것 같지만... 문제를 푸시려고 고민해보신 분들이라면 이해 할 것이라고 믿는다....(죄송)

 

그렇게 되면 위 두 경우를 제외하고 다음 두 경우만 생각해서 코드를 짜면 된다.

 

 

def solution(routes):
    routes.sort(key=lambda x:x[1])
    cam = [routes[0]]
    for i in range(1, len(routes)):
        drive_in = routes[i][0]
        last_cam = cam[len(cam)-1]
        last_cam_in, last_cam_out = last_cam[0], last_cam[1]

        if last_cam_out < drive_in:
            cam.append(routes[i])
        else:
            if drive_in < last_cam_in:
                pass
            else:
                cam[len(cam)-1] = [drive_in,last_cam_out]

    return len(cam)