[Python3]프로그래머스_단속카메라

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42884

접근법

익숙한 형태의 문제였는데 쉽게 떠오르지 않아서 이런 저런 예시들을 손으로 그려가면서 고민했다.
구간을 가지는 입력값들은 대체로 정렬을 통해 차례로 접근하는 문제들이 많다.
1. 진입구간으로 정렬
2. 진출구간으로 정렬

진출구간으로 정렬한다면 다음 차례의 차량은 두 가지 케이스가 있다.
(현재 진출구간에 카메라를 설치하면 다음 차량들의 시작점들이 현재 진출구간보다 작거나 같다면 모두 만날 수 있기 때문에 진출구간으로 정렬했다.)

1. 다음 차량 진입구간이 현재 차량의 진출구간보다 작거나 같은 경우

• 이때는 현재 차량의 진출구간에 카메라를 설치하면 두 차량을 모두 만날 수 있다.

2. 그 반대의 경우

• 이때는 카메라 한대로는 두 차량을 모두 만날 수 없으므로 새로운 카메라를 설치해야 한다.

코드

def solution(routes):
    answer = 1
    routes.sort(key=lambda x:x[1])
    end = routes[0][1]
    for i,j in routes:
        if( i > end ):
            answer += 1
            end = j
    return answer