[프로그래머스/Python] 단속카메라 - Level3

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

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

최소 카메라를 설치해야하므로 그리디 방식으로 나간 시점 기준으로 확인한다. 두 풀이 모두 진출시점 기준으로 작성된 코드이다.

 

첫번째 풀이

- 카메라에 걸리는지 확인하는 check 리스트를 두고 모든 구간을 검사하는 방법

def solution(routes):
    answer = 0
    length = len(routes)
    check = [0] * length # 카메라에 걸리는지 확인하는 리스트
    
    routes.sort(key = lambda x: x[1]) # 진출 시점 기준으로 정렬
    
    # 모든 구간을 돌면서 확인
    for i in range(length):
        if check[i] == 0:
            camera = routes[i][1]
            answer += 1
            
        for j in range(i+1, length):
            if routes[j][0] <= camera <= routes[j][1] and check[j] == 0:
                check[j] = 1
    
    return answer

check 는 카메라에 걸리는지 확인하는 리스트이다. 값이 0이면 카메라에 걸리지 않은 상태이고, 1이면 카메라에 걸린 상태이다.

전출 시점을 기준으로 확인하기 때문에 routes를 진출 시점 기준으로 정렬한다.

반복문을 통해 모든 구간을 돌면서 카메라에 걸리는지 확인한다. check[i] == 0 이면 카메라에 걸리지 않은 상태이므로 이 위치를 카메라 위치로 설정한다. 그 다음 반복문을 돌면서 카메라에 걸리는지 모든 구간을 확인한다. 카메라에 걸린다면 check[j]을 1로 바꾼다.

 

이 방법은 시간 복잡도가 O(n^2) 이기 때문에 효율성은 떨어지는 방법이다.

 

두번째 풀이

- camera 변수를 두어 위치를 갱신하면서 카메라에 걸리는지 확인하는 방법

def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[1]) # 진출 시점 기준으로 정렬
    camera = -30001 # 카메라 위치

    # 카메라 위치를 갱신하며 최소 카메라 개수를 찾음
    for route in routes:
        if camera < route[0]:
            answer += 1
            camera = route[1]
            
    return answer

차의 진입 시점과 진출 시점이 -30000 ~ 30000 이므로 카메라 위치를 의미하는 camera 변수를 -30001로 초기화한다.

반복문을 돌면서 카메라 위치를 갱신하며 최소 카메라 개수를 찾는다. 카메라의 위치가 갱신될 때마다 카메라가 새로 설치된 것이므로 answer에 +1을 해준다.

 

이 코드가 간결하고 훨씬 직관적으로 이해하기 쉬운 것 같다.