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

https://programmers.co.kr/learn/courses/30/lessons/42884

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

# 그리디문제이다.

 

def solution(routes):
    # routes를 나간시간 순으로 오름차순 정렬
    routes.sort(key = lambda x: x[1])
    answer = 1
    # camera = 현재 카메라가 설치된 위치
    camera = routes[0][1]
    
    # 두번째 차량부터 마지막번째 차량까지 반복문을 돌며 현재 카메라가 설치된 시간보다
    # 들어온 시간이 늦으면 camera에 현재 차량의 나간시간을 넣어주고 answer 1증가
    for i in range(1, len(routes)):
        if camera < routes[i][0]:
            camera = routes[i][1]
            answer += 1
                
    return answer

(프로그래머스 level: 3)

 

 

# 반복문을 돌며 카메라를 설치하는 것은 다음 그림과 같다.  (입력: [[-20,15], [-14,-5], [-18,-13], [-5,-3]])

 

1. 우선 routes배열을 나간시간기준 오름차순 정렬하면 다음과 같다. ([-18,-13], [-14,-5], [-5,-3], [-20,15])

2. camera 한개를 처음 나간차량의 나간시간에 설치한다. (-13)

3. 두번째 차량부터 들어온시간과 camera가 설치되어 있는 시간과 비교해서 들어온시간이 더 먼저이면

    다음 차량확인, 아니면 현재 차량의 나간시간에 다음 카메라를 설치하고 answer 1증가.

    -> 두번째 차량의 들어온 시간이 camera1이 설치되어있는 시간보다 먼저이므로 넘어가고

         세번째 차량의 들어온 시간이 -13보다 늦으므로 camera2를 나간시간 -3에 설치한다.

         네번째 차량의 들어온 시간은 -3보다 먼저이므로 넘어간다.

4. 네번째 차량까지 모두 확인했으므로 answer을 return해준다.