[프로그래머스/Level3] 단속카메라(Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42884

문제 접근

해당 문제는 범위 계산 문제이다.

1. 첫 아이템을 기준으로 삼고,
2. 아이템을 순회하며 아이템의 시작점이 범위 안에 있다면 아이템의 끝 점이 범위 끝보다 작은지를 체크해야함(범위를 좁혀가야함)
3. 아이템이 범위를 벗어나면 해당 아이템이 새로운 범위의 기준이 됨

소스 코드

최초로 푼 소스 코드

from typing import List
from collections import deque


def solution(routes: List[List[int]]):
    answer = 0
    
    routes.sort(key = lambda x: (x[0], x[1]))
    q = deque(routes)
    while q:
        answer += 1
        cur_start, cur_end = q.popleft()
        while q:
            next_start, next_end = q[0]
            if cur_end < next_start:
                break
            else:
                cur_end = min(cur_end, next_end)
                q.popleft()
        
    return answer

개선한 코드

from typing import List


def solution(routes: List[List[int]]):
    answer = 1
    
    routes.sort(key = lambda x: (x[0], x[1]))
    cur_start, cur_end = routes.pop(0)
    
    for route in routes:
        next_start, next_end = route
        if next_start <= cur_end:
            cur_end = min(cur_end, next_end)
        else:
            answer += 1
            cur_end = next_end
        
    return answer