[Python/파이썬] 프로그래머스 단속카메라

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

코드

def solution(routes):
    routes.sort()
    section = []
    for r in routes:
        if not section or section[-1][1] < r[0]:
            section.append(r)
        else:
            section[-1][0] = max(section[-1][0], r[0])
            section[-1][1] = min(section[-1][1], r[1])
    return len(section)

 

이 풀이는 쉽게 말하자면 겹치는 구간을 구한다고 생각하면 편하다. 

문제의 예시로 나왔던 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]]을 넣고 돌려보면 `section`이 결국 [[-18, -15], [-5, -5]]이 나오게 된다. 이 구간들에 각각 단속카메라를 하나씩 설치하면 모든 차량이 한 번은 단속카메라를 만나도록 할 수 있게 된다.  

더 나은 코드

def solution2(routes):
    answer = 0
    routes.sort(key=lambda x: x[1])
    prev = -30000
    for r in routes:
        if r[0] > prev:
            answer += 1
            prev = r[1]
    return answer

채점 결과를 보면 모든 테스트 케이스에서 이 방법이 더 빠른 것을 볼 수 있다.

처음에 구현했던 방법에서는 구간을 매번 갱신해주는 과정에서 `max`와 `min` 연산도 하고, 리스트에 요소를 추가하거나 기존 요소를 업데이트하는 부분이 있었기에 더 느렸던 것 같다.