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

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

 

문제 설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

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

제한사항

차량의 대수는 1대 이상 10,000대 이하입니다.
routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

입출력 예 설명
-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

 

---

[내 풀이]

- 첫 시도(12분) : 실패
- 두번째 시도(5분) : 수정 후 성공 (if ne<e 추가)

- 그림을 그려 생각하면 편하다. 

from collections import deque
def solution(routes):
    routes.sort()
    routes = deque(routes)
    s, e = routes.popleft()
    cnt = 1
    print(routes)
    while routes:
        ns, ne = routes.popleft()
        if ne < e:
            e = ne
        if e < ns:
            cnt += 1
            s, e = ns, ne
    return cnt

 

 

---

[대표 풀이]

- 어차피 카메라는 루트의 끝 부분에 설치하게 되니까, 그냥 routes[1] 을 기준으로 정렬하면 더 알고리즘이 깔끔해진다. 어떻게 routes[1] 기준으로 정렬하려고 하셨을까 신기했다. 보고나니 카메라가 설치되는 위치를 기준으로 체크하면 됐겠다 하고 바로 생각났지만, 처음 풀 땐 떠올리기 어려웠다. 

- 이 풀이를 보고 다시 내 풀이를 보니 e = ne 로 교체하는 부분이, 더 작은 e가 있으면 그 값이 다시 새로운 기준이 된다는 뜻이니까 가장 작은 e에 카메라가 꽂힌다는 의미이고, 이 점을 빨리 눈치챘더라면 코드를 다시 짰을 수도 있었겠다는 생각이 들긴 한다. (기준은 최대한 일관적인 게 좋을테니까).

def solution(routes):
    routes = sorted(routes, key=lambda x: x[1])
    last_camera = -30000

    answer = 0

    for route in routes:
        if last_camera < route[0]:
            answer += 1
            last_camera = route[1]

    return answer