Level 3 단속카메라 Python3

https://programmers.co.kr/learn/courses/30/lessons/42884?language=python3 

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

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_단속카메라.py

hwayeon351/Programmers-Algorithms

def solution(routes):
    routes.sort(key = lambda x:x[0], reverse = True)
    camera = routes[0][0]
    answer = 1
    for i in range(1, len(routes)):
        if camera in range(routes[i][0], routes[i][1]+1):
            continue
        camera = routes[i][0]
        answer += 1
            
    return answer

---

풀이 과정

풀이 시간 18분

되도록 차량 여러대가 통과하는 위치에 카메라를 설치하는 것이 카메라의 설치 횟수를 줄일 수 있는 방법이라고 생각했다.

문제에서 진입/진출 지점에 카메라가 있는 경우에도 차량이 카메라를 만났다고 간주한다는 조건이 있기 때문에, 차량의 진입 지점에 카메라를 설치해 나가는 방식으로 구현하였다.

차량의 진입 지점을 기준으로 내림차순으로 정렬하여 순차적으로 탐색하면서 현재 차량의 route가 이전에 설치한 카메라를 거치는지 여부를 판단하여 거친다면 카메마를 설치하지 않고, 거치지 않으면 해당 차량이 카메라와 만날 수 있도록 해당 차량의 진입 지점에 카메라를 설치하는 방식으로 문제를 해결할 수 있었다.

def solution(routes):
    #차량의 진입 지점 기준으로 내림차순으로 정렬
    routes.sort(key = lambda x:x[0], reverse = True)
    #가장 나중에 진입한 차량의 진입 지점에 카메라를 설치
    camera = routes[0][0]
    answer = 1
    #1번 인덱스부터 마지막 인덱스까지 탐색
    for i in range(1, len(routes)):
        #마지막으로 설치한 카메라의 위치가 해당 루트 안에 위치하는 경우
        #해당 차량이 카메라를 만난 경우이므로 카메라를 추가 설치하지 않고 continue
        if camera in range(routes[i][0], routes[i][1]+1):
            continue
        #해당 차량이 카메라를 만나지 못했으므로, 해당 차량의 진입 지점에 카메라를 설치
        camera = routes[i][0]
        answer += 1
            
    return answer
#시간복잡도 = O(nlogn), 공간복잡도 = O(n)

코드를 살펴보면 바로 이전에 설치한 카메라의 위치가 route에 속하는지의 여부를 기준으로 카메라를 만나는지를 판별한다.

모든 차량이 카메라를 최소 한 번 이상만 통과하면 되기 때문에 해당 루트가 짧든 길든 간에 바로 이전에 설치한 카메라의 위치가 route에 속하는지만 따져주면 된다.

이 코드의 시간 복잡도는 처음 routes를 sort할 때 발생하는 O(nlogn)과 for문이 len(routes)-1만큼 반복된다.

따라서 시간복잡도 = O(nlogn) + O(n) = O(nlogn)이다.

공간복잡도는 routes의 크기만큼 할당되기 때문에 S(3n) -> O(n)이다.