프로그래머스 : 단속 카메라 (python)

프로그래머스 Level 3 : 단속 카메라

문제 링크

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

전체 코드

def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[1])

    idx = 0
    while idx < len(routes):
        s, e = routes[idx]

        idxx = 0
        for i in range(idx, len(routes)):
            if routes[i][0] <= e <= routes[i][1]:
                idxx += 1
            else:
                break
        
        if idxx != 0:
            answer += 1
        idx += idxx

    return answer

코드 작성시 고민했던 점과 배운 점

1. 그리디 문제이기 때문에 최적의 답을 도출하기 위한 고민

• 가장 먼저 든 생각은 카메라를 최소로 설치해야 하기 때문에 카메라를 설치해야하는 위치는 routes에 주어진 지점이라 생각했다.
  → 주어진 지점 중에서 카메라를 설치하려는 지점의 기준이 필요.
• 처음에는 진입 지점을 기준으로 잡아 진입 지점에 대해 정렬하고 답을 도출하려 했으나, 가장 먼저 진입한 차량의 진출 지점이 다른 차량의 진입 지점보다 크다면 최적의 답을 찾을 수 없었다.
  ex) 예외 테스트 케이스 : [[-100,100],[50,170],[150,200],[-50,-10],[10,20],[30,40]]
• 따라서 진입 지점이 아닌 진출 지점을 기준으로 정렬하였다.

    routes.sort(key=lambda x: x[1])

2. 카메라 설치를 설치하였을 때, 카메라와 만나는 차량을 구별하는 방법

• 가장 먼저 진출하는 지점에 카메라 설치, 카메라 설치 지점을 지나치는 모든 차량은 다음 카메라 설치에 대해서 신경을 쓰지 않아도 되는 차량이기 때문에 고려할 필요가 없어진다. 이 후 아직 카메라에 찍히지 않는 차 중 가장 먼저 진출하는 차량의 진출 지점에 카메라를 설치하면 된다. → 반복
• idx, idxx 변수를 사용하여, 카메라를 마주치는 차량이 있을 때마다 idxx에 1씩 더해주고 반복문이 다 돌았을 때 idx에 idxx를 더해 업데이트해주었다.

while idx < len(routes):
        s, e = routes[idx]

        idxx = 0
        for i in range(idx, len(routes)):
            if routes[i][0] <= e <= routes[i][1]:
                idxx += 1
            else:
                break
        
        answer += 1
        idx += idxx

추가로, 카메라를 설치하는 시점은 while문이 한번 돌때마다 카메라를 설치하기 때문에 idx 업데이트 시점에 answer도 1을 더해준다.

그외 고민했던 방법

• 반복문과 routes.pop(idx)을 통해 카메라와 마주치는 차량을 삭제해주며 routes가 empty 될 때까지 실행시키려 했으나, list.pop(idx) 은 평균 시간복잡도가 O(N)이기 때문에 pass!
• deque를 사용하여 popleft()를 통해 시간복잡도를 줄이며 구현하려 했으나, 반복문을 돌리면서 deque의 원소를 삭제하면 반복문의 index가 꼬일거 같아 pass!

결과