Lv3. 단속카메라

# 문제 설명

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

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

# 제한 사항

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

# 입출력 예

입출력 예 설명

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

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

문제 해결 시 고려사항

• 카메라 설치의 최적 위치 선정

본 문제는 주어지는 routes를 보고 모든 차량을 단속하기 위한 최소 단속카메라 개수를 구하는 문제이다.

최소의 카메라 수를 구하기 위해서 필자는 아래와 같은 과정을 거쳤다.

1. 주어지는 routes 리스트를 진입지점 기준으로 오름차순 정렬한다.
2. 오름차순 된 리스트 내의 가장 끝 차량부터 카메라를 설치해나가며 아래와 같이 검사한다
3. 반복 중 해당 차례의 차량이 카메라에 찍히지 않는다면, 해당 차례 차량의 진입지점에 카메라를 설치하고 아래와 같은 반복문을 통해 검사를 진행한다.
4. 위 반복에서의 차량 이전 차량들에 대해 현 카메라의 위치가 각 차량의 진입 지점과 진출 지점 사이에 존재한다면, check를 True(카메라에 찍힌다는 의미)로 바꾸어준다.

위의 과정을 코드로 변환하면 아래와 같다.

 answer = 0
     # 진입 지점의 제일 마지막부터 검사하기 위해 오름차순 정렬
     routes.sort()
     check = [0] * len(routes)
     # 오름차순 정렬(진입지점)된 차량 중 마지막 차량부터 카메라를 설치해나가며 검사
     for i in range(len(routes)-1,-1,-1):
         # i차량이 카메라에 찍히지 않는다면
         if check[i] == 0:
             # i 차량의 진입지점에 카메라 설치
             camera = routes[i][0]
             answer += 1
         for j in range(i,-1,-1):
             # i 지점 전 차량들 중 해당 차량의 진입 지점과 진출 지점 사이에 카메라가 존재한다면 check
             if check[j] == 0 and routes[j][1] >= camera >= routes[j][0]:
                 check[j] = 1

전체 코드

def solution(routes):
    answer = 0
    # 진입 지점의 제일 마지막부터 검사하기 위해 오름차순 정렬
    routes.sort()
    check = [0] * len(routes)
    # 오름차순 정렬(진입지점)된 차량 중 마지막 차량부터 카메라를 설치해나가며 검사
    for i in range(len(routes)-1,-1,-1):
        # i차량이 카메라에 찍히지 않는다면
        if check[i] == 0:
            # i 차량의 진입지점에 카메라 설치
            camera = routes[i][0]
            answer += 1
        for j in range(i,-1,-1):
            # i 지점 전 차량들 중 해당 차량의 진입 지점과 진출 지점 사이에 카메라가 존재한다면 check
            if check[j] == 0 and routes[j][1] >= camera >= routes[j][0]:
                check[j] = 1
    return answer