[프로그래머스] '단속카메라' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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

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

 

 

 

 

 

제한사항

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

 

 

입출력 예

routes	return
[[-20,15], [-14,-5], [-18,-13], [-5,-3]]	2

알고리즘 분석

 

• 나의 풀이

def solution(routes):
    answer = 0
    a_min = min([routes[x][0] for x in range(len(routes))])
    a_max = max([routes[x][1] for x in range(len(routes))])
    arr_route = [x for x in range(a_min, a_max+1)]

    while routes:
        arr = []
        for a in range(a_min, a_max+1):
            count = 0
            for route in routes:
                if route[0] <= a <= route[1]:
                    count += 1
            arr.append(count)
        point = arr_route[arr.index(max(arr))]
        tmp = []
        for route in routes:
            if route[0] <= point <= route[1]:
                pass
            else:
                tmp.append(route)
        routes = tmp[:]
        answer += 1
    return answer

 

내 코드는 route 진입/진출 지점 중에 최저 구간에서 최고 구간까지 구간마다 몇개의 route가 겹치는지 검사한 후에 리스트에 목록을 저장합니다. 그리고 그 중에 가장 많이 겹치는 구간에 카메라를 설치하고 더 이상 단속카메라가 필요없는 route는 목록에서 삭제합니다. 

 

이 코드는 정확성 검사는 통과했지만 효율성 검사에서 떨어졌네요.

일단 너무 복잡한 코드이기도 소요되는 시간도 너무 많은게 문제점인 것 같습니다.

 

 

• 블로거의 코드 

출처 : https://m.post.naver.com/viewer/postView.nhn?volumeNo=26958545&memberNo=33264526

[Python] 프로그래머스. 단속카메라 (Level 3)

def solution(routes):
    # 도로의 맨 앞에서부터 감시카메라 설치.
    routes = [[i[0], i[1]] for i in sorted(routes, key = lambda x: (x[0]))]
    result = [routes.pop(0)]
    for compare in routes:
        idx = 0
        while idx != len(result):
            # 만약 새 차량의 진입시점 / 진술시점이 기존 카메라 설치 범위에 들어간다면
            if (result[idx][0] <= compare[0] <= result[idx][1]) or (
                    result[idx][0] <= compare[1] <= result[idx][1]
            ):
                # 감시 카메라가 새 차량을 감지할 수 있도록 감시 카메라의 위치 조정
                result[idx][0] = compare[0] if compare[0] > result[idx][0] else result[idx][0]
                result[idx][1] = compare[1] if compare[1] < result[idx][1] else result[idx][1]
                break
            else:
                idx += 1
        # 만약 감시카메라 설치 위치를 전부 돌았는데도 감지가 안된다면
        # 차량을 감시할 수 있는 새 감시카메라를 설치해야 한다.
        if idx == len(result):
            result.append(compare)
    return len(result)

결국 혼자 풀지못해서 다른 사람의 풀이를 참고했습니다. 

이 풀이의 경우, 저와 비슷하지만 완전히 다른 방식으로 풀었는데 제가 모든 구간에서의 겹치는 경우의 수를 구했다면

이 풀이는 route가 겹치는 구간의 범위를 점차 좁혀나가는 식으로 풀이 했습니다. 

예를 들어, 두 구간의 진입/진출 범위 중에 겹치는 부분이 있다면 그 부분이 감시카메라가 존재할 수 있는 구간이며, 다음 구간과 비교할 때는 이 겹치는 구간과 비교합니다. 겹치는 구간과 한 구간이 겹치는 부분이 있다면 세 개의 구간이 완전히 겹치는 구간이 있다는 의미입니다. 즉, 완전히 겹치는 이 구간에 감시카메라가 존재할 수 있습니다. 

만약 더이상 겹치는 구간이 없다면 새로운 감시카메라를 설치해줍니다. 

 

이 코드의 경우, 실행 시간이 매우 짧았으며 효율성 검사도 무사히 통과하는 모습을 보여줬습니다. 

 

 

• Most 1의 풀이

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

 

솔찍히, 이 코드를 첨 봤을 때 너무 허탈했다.

이렇게 쉬운 풀이가 있을 줄이야... 

 

위의 코드의 경우, route[x][0]을 기준으로 정렬했다면, 

해당 코드의 경우, route[x][1]을 기준으로 정렬했습니다. 

 

그 이유는 last_camera에 route[x][1] 값이 들어가며 다음 구간의 route[x][0]의 값과 비교하기 때문입니다.