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

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

코딩테스트 연습 - 단속카메라

 

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

routesreturn

[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]

2

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

 

 

 

카메라를 어떻게 하면 모든 차들이 한번씩 다 지날지 최소개수를 구하는 문제였다.

 

처음에는 노드로 보아서 트리나 그래프를 생각했었는데, 간선이 연결된다기 보다는 일직선상에서 겹치는 부분을 고려해야 하는 문제라 접근방식이 아닌것 같았다.

 

그래서 서로 겹치는 범위를 비교하는 방향으로 문제를 풀이했다.

 

현재 구간과 겹치는 부분이 있으면 더 이득을 볼 수 있으니 겹치는 구간만 따로 저장해서 다음 구간과 비교하고

 

겹치는 부분이 없으면 더이상 카메라 1대로 이득을 볼 수 없으니 카메라 개수를 추가하고 새로운 구간으로 현재구간을 변경한다.

 

다만 여기서 주의해야 할 부분은 마지막 부분인데, 마지막구간이 여러 자동차가 겹쳐진 구간이든, 아니면 새로운 1개의 자동차 구간이든 카메라는 공평하게 1대가 더 있으면 된다. 그러므로 마지막에 +1을 해주는 것이 맞다.

 

 

def solution(routes):

    routes.sort()
    #겹치는 범위 정하기
    start,end=routes[0]
    #카메라 개수
    camera=0
    for i in range(1,len(routes)):
        #1. 안겹치는 경우
        if end<routes[i][0]:
            camera+=1
            start,end=routes[i]
        #2. 절반만 겹치는 경우 겹치는 범위로 변경해줌.
        elif  routes[i][0]<=end<=routes[i][1]:
            start=routes[i][0]
        else:
            start,end=routes[i]
    return camera+1