찬우의 이것저것 Chanwoo's blog

[프로그래머스 python]과속카메라

2020-04-17

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 이하입니다.
routes return
[[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2

routes 안의 모든 경로를 정렬하면 중복되는 경로를 찾기 수월해진다.

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

중복되는경로 어디에 카메라를 놓던 상관 없지만 계산을 편하게 하기위해 나가는곳에 카메라를 놓는다고 가정

-20~15 -> 15

-18~-13 -> -13

-14~-5 -> -13 (-13, -5 비교해서 더 작은)

-5 -3 -> 마지막 카메라위치 -13이 범위안에 없어서 새 카메라를 -3에 설치

-13, -3에 카메라를 설치하게된다. (position에 카메라가 설치된 위치를 저장해봤다.)



def solution(routes):
    routes = sorted(routes)
    position = []

    ans = 0
    camera = 30001

    for r in routes:
        if r[0] <= camera:
            camera = min(r[1], camera)
        else:
            ans += 1
            position.append(camera)
            camera = r[1]
    ans+=1
    position.append(camera)

    # print(position)
    return ans


if __name__ == '__main__':
    routes = [[-20, 15], [-14, -5], [-18, -13], [-5, -3]] # 2
    # routes = [[1,3]]
    print(solution(routes))

    # more test case
    print(solution([[-2, -1], [1, 2], [-3, 0]]))  # 2
    print(solution([[0, 0]]))  # 1
    print(solution([[0, 1], [0, 1], [1, 2]]))  # 1
    print(solution([[0, 1], [2, 3], [4, 5], [6, 7]]))  # 4
    print(solution([[-20, -15], [-14, -5], [-18, -13], [-5, -3]]))  # 2
    print(solution([[-20, 15], [-14, -5], [-18, -13], [-5, -3]]))  # 2
    print(solution([[-20, 15], [-20, -15], [-14, -5], [-18, -13], [-5, -3]]))  # 2

참조

https://minnnne.tistory.com/28

Related Posts