프로그래머스 단속카메라 파이썬

프로그래머스 파이썬 단속카메라 프로그래머스 단속카메라 파이썬 파이썬 프로그래머스 단속카메라 파이썬 단속카메라 프로그래머스 단속카메라 프로그래머스 파이썬 단속카메라 파이썬 프로그래머스

단속카메라

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

문제 단순화

• 차량의 이동경로들이 있다.
• 해당 이동경로들이 한 번씩 지나도록 카메라를 설치할 때, 필요한 최소 카메라의 갯수를 리턴한다.

문제풀이

• 이동경로 routes를 정렬한다.
• 첫번째 이동경로부터 시작해서, 해당 이동경로가 카메라 설치경로가 된다.
• 카메라 설치 경로에 다음 이동경로의 최소값이 포함되어 있는 지 검사한다.
• 최소값이 포함되어 있으면, 중복된 이동경로로 카메라 설치경로를 갱신한다.
• 최소값이 포함되지 않으면, 카메라 개수를 추가하고 해당 이동경로가 다음 카메라 설치경로가 된다.
• 모든 경로를 탐색하면, 카메라 개수를 리턴한다.

코드

def solution(routes):
    answer = 0
    routes.sort()
    end = routes[0][1]
    for i in range(1,len(routes)):
        if end < routes[i][0]:
            answer += 1
            end = routes[i][1]
        end = min(end, routes[i][1])
    return answer+1