[프로그래머스] 단속카메라 - Python3

1. 문제 설명

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

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

제한사항

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

입출력 예

routesreturn

[[-20,15], [-14,-5], [-18,-13], [-5,-3]]

2

입출력 예 설명

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

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

 

출처: programmers.co.kr/learn/courses/30/lessons/42884

 

2. 접근 방법 및 풀이

- 그리디 알고리즘은 항상 '첫 단추를 어떻게 끼우는가' 가 성공과 실패를 가르는 것 같다. 30분간의 고민 끝에 나온 아이디어는 "가장 먼저 고속도로를 빠져나가는 녀석부터 카메라를 달자!" 였다.

 

마음의 눈으로 보십쇼..

- 테스트 케이스를 그림으로 그려보았다! 이를 아이디어에 맞게 정렬해보자.

 

eye of mind...

- 위쪽부터 차례대로 보면서 cam을 두는 방식이다! 세세한 부분은 코드에 주석으로 달아보도록 하겠습니다.

 

def solution(routes):
    
    cam_arr = [] 
    # 도착 지점으로 오름차순 정렬
    routes = sorted(routes, key = lambda x: x[1])
    
    # 첫 번째 cam 지정
    cam = routes[0][1]
    cam_arr.append(cam)
    
    for i in range(1, len(routes)):
        # 다음 경로안에 cam이 있다면
        if routes[i][0] <= cam and cam <= routes[i][1]:
            continue
        # cam이 밖에 있다면
        else:
            # 다음 경로 도착지점을 cam으로 지정
            cam = routes[i][1]
            cam_arr.append(cam)
    
    answer = len(cam_arr)
    
    return answer