[고득점 Kit(탐욕법)] 단속카메라 (Python)

코딩테스트 연습 - 단속카메라

 

 

풀이

 차량의 진입/전출에 따른 범위를 그림으로 그려서 판단하면 쉽게 해결 가능하다. 먼저 입력으로 주어진 routes를 전입을 기준으로 오름차순 정렬을 한다. 그 후 다음과 같이 경우를 나누어 for문을 돌면서 이에 맞게 처리를 해주면 된다. 먼저 처음 차량의 범위에 단속카메라를 설치한다고 가정하고 시작한다. 

 참고로 카메라의 설치 범위에서 시작 부분은 따로 신경쓰지 않는다. 어차피 정렬을 하고 나면 진입 지점은 항상 뒤일 것이기 때문에 카메라의 설치 범위 역시 그에 맞춰서 좁아진다고 생각하면 된다.

 

(1) 다음 차량의 진입 지점(nowStart)이 이전 차량의 전출 지점(prevEnd)보다 뒤일 경우 (prevEnd < nowStart)

 현재 단속카메라는 빗금친 부분에 설치되어있다. 다음 차량의 진입 지점이 이전 차량의 전출 지점보다 뒤일 경우에는 겹쳐지는 이동 경로가 없으므로 다음 차량을 위해서는 단속카메라를 새로 설치해야 한다. 그러므로 새로 단속카메라를 설치해야한다.

 

 

(2) 다음 차량의 진입 지점(nowStart)이 이전 차량의 전출 지점(prevEnd)보다 앞일 경우 (prevStart < nowStart)

-> 이 경우는 다음 차량의 전출 지점(nowEnd)에 따라 두 가지로 나뉜다. 

 

(2-1) 다음 차량의 전출 지점(nowEnd)이 이전 차량의 전출 지점(prevEnd)보다 뒤일 경우 (prevEnd < nowEnd)

 이 경우 위의 빗금친 부분에 설치하면 단속카메라 한 대로 두 대의 차량을 단속할 수 있다. 추가로 nowEnd와 prevEnd가 같은 경우도 있는데 이를 포함하여 해당 경우에는 따로 작업이 필요하지 않다. 이미 범위가 prevEnd로 설정되어 있기 때문이다.

 

(2-2) 다음 차량의 전출 지점(nowEnd)이 이전 차량의 전출 지점(prevEnd)보다 앞일 경우  (nowEnd < prevEnd)

 이 경우 위의 빗금친 부분에 설치하면 단속카메라 한 대로 두 대의 차량을 단속할 수 있다.

 

 

 이렇게 단속카메라의 범위를 추적하여 다음 차량을 단속할 수 있는지 체크한다. 만약 단속할 수 없다면 새로운 단속카메라를 설치하고 범위를 수정하는 방식으로 진행하면 답을 구할 수 있다.

 

 

코드

def solution(routes):
    routes.sort(key = lambda x: x[0])

    # 단속카메라를 처음 차량의 범위에 설치한다.
    # 시작 위치는 저장하지 않았는데 이유는 routes를 정렬했기 때문에
    # 다음 차량의 진입 지점이 더 뒤에 있을 것이 보장되기 때문이다.
    prevEnd = routes[0][1]
    answer = 1 

    for i in range(1, len(routes)):
        nowStart = routes[i][0] # 다음 차량의 진입 지점
        nowEnd = routes[i][1]  # 다음 차량의 전출 지점 

        # 위의 설명 (1)에 해당 하는 경우
        # 새로운 카메라를 설치하고 카메라의 마지막 지점을 nowEnd로 설정한다.
        if prevEnd < nowStart:
            prevEnd = nowEnd
            answer += 1
        
        # 위의 설명 (2-2)에 해당 하는 경우
        # 새로 카메라를 설치할 필요 없이 카메라의 마지막 지점을 nowEnd로 좁혀준다.
        # (2-1)의 경우에는 이미 카메라의 마지막 지점이 더 앞에 있는 prevEnd이기 때문에
        # 다른 작업을 추가로 할 필요가 없다.
        elif nowStart < prevEnd and nowEnd < prevEnd:
            prevEnd = nowEnd
        
    return answer