[코딩 테스트] 프로그래머스 - 단속 카메라(Lv.3) in Python

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

 

더 자세한 설명- programmers.co.kr/learn/courses/30/lessons/42884 

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

 

풀이

1. 먼저 routes을 시작점 (원소[0]) 기준으로 오름차순 정렬.

2. minPos = 첫번째원소[0], maxPos = 첫번째원소[1]로 설정해준다.

 

3. 주어진 routes의 모든 원소를 탐색할 때까지

3-1. 다음 원소의 최솟값이 현재 maxPos가 크다면

  => 서로 겹치지 않는다는 뜻.

       (참고 - 다음 원소의 최댓값이 현재 minPos보다 작아도 겹치지 않는 상황, but 이미 routes를 최솟값기준 오름차순 정렬해줬기 때문에, 그럴 일은 없을 것이다.)

  => 겹치지 않는다면, 새로운 카메라가 어차피 필요한 상황.

  => answer +=1 으로 카메라 수 더해줌

  => minPos = 다음원소[0], maxPos = 다음원소[1]으로 업데이트.

3-2. 다음 원소의 최솟값이 현재 maxPos보다 크지 않다면

  => 서로 겹친다는 뜻.

  => 겹치는 범위 안에서, minPos는 현재 minPos와 다음원소[0] 중 더 큰 값, maxPos는 현재 maxPos와 다음원소[1] 중 더 작은 값으로 conservative하게 설정.

 

4. 현재 answer에 1을 더한 것이 정답이다.

 

예시: routes = [[0,5], [1,6], [6,8]]일 때,

 

1. [0, 5] 탐색

2. [1, 6] 탐색

minPos = 1, maxPos = 5

3. [6, 8] 탐색

 

기존 범위와 (minPos - maxPos, 1 - 5) 안 겹치므로, 기존 범위에 필요한 카메라 1대를 answer에 추가

4. 탐색이 끝난 후, 마지막 탐색하던 구간도 카메라가 필요하니, answer에 1을 더한 값을 최종 답으로 리턴!

 

 

 

 

 

코드구현

def solution(routes):
    answer = 0
    # sort
    routes.sort(key = lambda x: x[0])
    minPos = routes[0][0]
    maxPos = routes[0][1]
    
    for x in routes:
        # if no overlap
        if x[0] > maxPos:
            minPos = x[0]
            maxPos = x[1]
            answer += 1
        else:
            minPos = max(minPos, x[0])
            maxPos = min(maxPos, x[1])
    answer +=1
    
    return answer