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

문제

---

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

https://school.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 이하입니다.

입출력 예

routesreturn

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

2

• 차량들의 시작,도착지점이 주어졌을 때 겹치게 만들 수 있는 최소 갯수를 구하는 것이다.
• N개를 설치한다고 할 때 모두 단속 할 수 있을까?로 부터 아이디어를 시작하여 보았다.

위 아이디어로 시작하였을 때 생각하지 못한 부분이 있다.

공통된 범위에 있지만, 겹치지 않은 반례가 생긴다.

[[-30,30],[-20,20],[30,40]] 의 경우에는 2가지의 경우이다.

 

알고리즘

---

위 문제를 해결하기 위해 시작범위를 갱신 해주는 코드를 추가하였다.

1. Deque로 정렬을 한다.

2. 현재 시작하는 범위에서 갈 수 있는 범위를 포용한다.

3. 갱신하는 경우는 현재 시작범위 X 가 현재 Start 값의 Y보다 작은 경우 -> 정답 1개 증가 , 갱신

4. 그렇지 않다면, 현재 시작범위 Y와 현재 Start Y와 비교하여 작은 값으로 갱신하여 준다. 

5. Deque에 값이 없을 때 까지 3-4를 반복

 

코드

---

from collections import deque

def solution(routes):
    answer = 0
    x,y = 0,1
    n = len(routes)
    start = [-30001,-30001]
    
    routes=deque(sorted( routes , key = lambda x:(x[0],x[1])))

    while routes :
        if start[y] < routes[0][x] :
            answer+=1
            start = routes.popleft()
        else:
            temp_x,temp_y = routes.popleft()
            start[y] = min(temp_y , start[y])
            
    return answer

 

코드 리뷰

---

• 정렬을 해두었기 때문에 이미 한번 본값에 대해서는 별도로 처리를 안해주어도 된다.
• 그럼으로 Deque와 while 문 보다는 한번씩 보고 갱신하여 주는 코드로 처리한다.
• Y값을 기준으로 갱신을 처리할 수 있다.

def solution(routes):
    answer = 0
    start = -30001

    routes = sorted( routes , key = lambda x:x[1])
    for route in routes :
        if start < route[0] :
            answer+=1
            start = route[1]
            
    return answer