프로그래머스(programmers) 단속카메라 python 정답 [Greedy Algorithm]

프로그래머스(programmers) 단속카메라 python 정답 [Greedy Algorithm]

문제 링크

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

프로그래머스

문제 정답

입출력 예

routes	return
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	2

정답 코드

def solution(routes):
    answer = 0
    # 무조건 만나야 하는 위치(종료 위치)
    # 핵심 기준점 정렬
    sorted_routes = sorted(routes,key=lambda x : x[1])    
    prev =-30001
    for route in sorted_routes:
        if prev < route[0]:
            answer +=1
            prev = route[1]            
    return answer

문제 해설

일단 routes를 종점 기준으로 정렬한다.

해당 종점 전까지는 카메라 설치를 최대한 늦출 수 있기 때문이다.

 

그럼 언제 카메라를 설치하면 될지 알아보자

아래 그림을 예로 들겠다.

다음과 같이 1번의 마지막에 카메라를 설치하는 것은 확정적이다.

마지막에 설치해야 최대한 prev아 앞에 있는 route들의 카메라 설치를 미룰 수 있다.

이 점을 prev로 기억한다.

answer +=1
prev = routes[1] # 뒷점

이 prev점은 2와 3의 시작점보다 뒤에 있다

따라서 2와 3을 처리할 때는 카메라를 설치할 필요가 없다

(prev >=route[0])

 

하지만 이 prev점은 4의 시작점 보다 앞에 있다.

따라서 카메라를 하나 더 설치해야 한다.

이 경우 카메라를 가장 적게 설치하려면 1번과 동일하게 4의 마지막에 설치하면 된다.

answer +=1
prev = routes[1] # 뒷점

이 논리를 반복해서 처리하면 답이 나온다.

시간복잡도는 정렬에 의한 O(nlogn)이다.