[Python] 탐욕법(3) 단속카메라

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

아이디어

1. 가장 왼쪽에서 오는 경로부터 탐색하기 위해 routes를 왼쪽을 기준으로 정렬합니다.
2. 그리고 첫 번째 경로의 오른쪽 좌표를 저장하고 해당 경로에 카메라를 배치합니다.
3. 경로들은 세 가지 관계를 갖습니다. (완전 겹쳐진 경우, 한쪽만 겹쳐진 경우, 아예 안 겹치는 경우)
4. 왼쪽 좌표 기준으로 정렬했기 때문에 오른쪽 좌표를 기준으로 경로들을 비교합니다.
5. 완전 겹쳐진 경우에는 카메라가 이미 있기 때문에 카메라는 추가하지 않고 오른쪽 좌표만 바꿔줍니다.
6. 한 쪽만 겹쳐진 경우에는 해당 경로가 없다고 가정하고 넘어갑니다.
7. 아예 겹쳐지지 않는 경우에는 카메라가 있을 수 없기 때문에 카메라를 추가하고 오른쪽 좌표도 바꿔줍니다.
8. 좌표를 그려보고 경로들의 관계를 파악하여 풀어야하는 문제였습니다.

정답 코드

def solution(routes):
    routes = sorted(routes, key= lambda x : x[0])
    ex_right = routes[0][1]
    camera = 1

    for L, R in routes:
        if R <= ex_right:
            ex_right = R
        if L <= ex_right < R:
            pass
        if ex_right < L :
            ex_right = R
            camera+=1

    return camera