[Python] 단속카메라

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

프로그래머스

문제설명

 

 

접근법

• 최대한 많이 겹치는 구간에 카메라를 놓으면 된다.
• 최대한 많이 겹치는 구간은 어딜까? i 번째 차량과 i+1번째 차량이 겹치는 구간 중 가장 뒷 부분에 카메라를 놓으면 된다.
• 가장 최신에 놓은 카메라 위치를 update하면서 "진입 시점 <= 카메라 위치 <= 진출 시점"에 만족하는 차량에 대해서는 카메라 위치 update를 하지 않는다.
• 위 조건에 만족하지 않는다면 카메라에 찍히는 순간이 없는 것이기 때문에 카메라 개수를 1 증가시키고, 해당 차량의 진출 시간으로 카메라 위치를 update시킨다. 

def solution(routes):

    routes.sort(key=lambda x : x[1])
    
    answer = 1
    cur_camera = routes[0][1]
    for i in range(1, len(routes)):
        if cur_camera >= routes[i][0] and cur_camera <= routes[i][1]:
            continue
        else:
            answer += 1
            cur_camera = routes[i][1]
            
    return answer

 

---

처음 생각했던 알고리즘의 문제점(틀린이유)

Try1

카메라는 어느 한 시점에 존재하는데 구간으로 겹치는 지 여부를 결정하였다. 

def solution(routes):

    routes.sort(key=lambda x : x[1])
    
    answer = 1
    cs = routes[0][0]
    ce = routes[0][1]

    for i in range(1, len(routes)):
        # 현재 가장 최신 카메라 경로에 있는지
        if (routes[i][0]>= cs and routes[i][0] <= ce) or (routes[i][1] >= cs and routes[i][1] <= ce):
            continue
        else:
            answer += 1
            cs = routes[i][0]
            ce = routes[i][1]
            
    return answer

 

사용된 알고리즘

그리디 알고리즘