손가락놀이터

문제 후기

1. 처음에는 단순하게 진입 지점과 진출 시점을 기준으로 카메라를 설치하려했습니다. 해당 방법으로 했더니 정답 자체가 아니어서 알고리즘이 틀린 것으로 알게 됐다.

2. 2번째로는 나가는 시점을 기준으로 카메라를 설치했다. 메모이제이션을 통해 미리 최대 길이(60,000)만큼 배열을 만들고 나가는 지점에 카메라를 기록하는 방식으로 했다. 정확성에서는 통과했지만 효율성에서 케이스 한 개가 안됐다.

3. 3번째로 새로운 카메라가 추가된 경우 미리 나머지 차량을 확인하는 방식을 선택했다. 해당 알고리즘으로 했을 때 효율성 또한 만족하는 것으로 나왔다.

문제 설명

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

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

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

def solution(routes):
    
    chk_camera = [0] * len(routes)      # 총 확인해야하는 차량 수
    count = 0   # 결과값
    routes.sort(key=lambda x:x[1])      # 진출 지점으로 정렬

    for car in range(len(routes)):
        # 만약 해당 차량이 카메라 테스트에서 통과한 경우 패스
        if chk_camera[car]:
            continue
        # 해당 차량이 지나가는 카메라가 없으므로 새로 만듬.
        camera = routes[car][1]
        count +=1
        
        # 새로 만든 카메라가 이후 차량 중에서 지나가는 차량이 있는지 확인
        for num in range(car + 1, len(routes)):
            if routes[num][0] <= camera <= routes[num][1]:
                chk_camera[num] = True

    return count