PG)단속 카메라 -lv3

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

프로그래머스

 

def solution(routes):
#     아이디어
# 정렬을 이용해야한다.
# 진입이 지점이 가장 작은 순부터
# 진출 시점을 기준으로 카메라를 설치한다.
    routes.sort(key=lambda x: (-x[1], -x[0]))
    routes = [routes[i] for i in range(len(routes)-1, -1, -1)]
    answer = 1
    last = routes[0][1]

    for i in range(1, len(routes)):
        if routes[i][0] <= last <= routes[i][1]:
            continue
        else:
            answer += 1
            last = routes[i][1]

    return answer

 

제법 쉬운 그리디 문제이다.

이 문제의 키포인트는 두가지이다.

진입 시점이 가장 작은 것부터 오름차순으로 정렬하고, 카메라를 설치하는 기준을 각 차량의 진출 시점으로 잡아야한다.

왜냐하면 진입시점이 가장 작은 것부터로 정렬했기 때문에 최대한 두 개의 차량이 겹치려면 진출 시점으로 잡아야 최적의 해를 만족하기 때문이다.