프로그래머스 Lv3 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42884

[나의 풀이]

⌛ 시간 초과

def solution(routes):
    from collections import deque
    import copy
    
    cases = deque([])
    cars = routes.copy()
    max_num = max(routes,key=lambda x:x[1])[1]
    min_num = min(routes,key=lambda x:x[0])[0]
    print("max_num : ",max_num )
    print("min_num : ",min_num )
    
    cases.append([cars,0])
    
    while cases:
        
        case = cases.popleft()
        cars, cameras = case
        
        for x in range(min_num,max_num+1) :
            # print(x)
            if start<=x and end>=x:
                
        # break
        
        
        if cars==0:
            return cameras
        else:
            pass
    return 0

그리디 문제입니다. 각 차량들의 이동 경로가 주어질 때, 차량마다 단속카메라를 1개씩 지나쳐야할 때의 최소 단속 카메라의 갯수를 구하는 문제입니다.🐓🐓🐓

문제를 이해하고 구현할 시에, 차량들의 최소 시작점과 최대 도착점을 구하고 이 모든 구간별로 BFS를 돌며 단속 카메라에 잡힌 차량들을 제거하며 단속되지 않은 차량이 0일 때의 경우의 수를 구하고자 하였습니다.

하지만 단속카메라를 설치할 수 있는 모든 경우의 수를 구현하는데 어려움이 있어 해결하지 못하였고 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

def solution(routes):
    routes.sort(key = lambda x : x[1])
    answer = 1
    prev_end = routes[0][1]
    for start, end in routes :
        if start > prev_end :
            answer += 1
            prev_end = end

    return answer

해결 포인트는 도착점을 정렬하며 for문을 도는 것이였습니다. 차량들의 이동 경로의 경우의 수를 살펴보면 크게 3가지였습니다.🐰🐰🐰

1) 차량과 차량간의 겹치는 부분이 없을 때
2) 한 차량의 이동경로가 다른 차량의 이동경로를 완전히 포함할 때
3) 차량과 다른 차량간의 이동 경로가 일부분 겹칠 때

입니다.

이 모든 경우의 수를 관통하여 최소의 수를 구할 수 있는 방법은 도착점을 기준으로 정렬하고 판단하는 것이였습니다.

도착점을 기준으로 정렬한 뒤,

1) 의 경우 한 차량의 도착점이 다른 차량의 시작점보다 반드시 작으므로 반드시 단속카메라가 +1 됩니다.
2) 의 경우 완전히 포함관계이므로 단속카메라가 추가되지 않아도됩니다.
3) 의 경우 한 차량의 도착점이 다른 차량의 시작점보다 작으므로 단속카메라가 추가되지 않습니다.

이와 같은 알고리즘으로 완전히 간결한 풀이로 해결한 것을 알게 되었습니다.

비교하는 경우의 수를 따져보며 도착점을 정렬한다는 아이디어를 생각해내기 힘들었던 문제였습니다.

[다른 사람의 풀이2]

def solution(routes):
    routes.sort(key=lambda x: x[0])
    a = 1
    m = 30_000
    for i, j in routes:
        if i > m:
            a += 1
            m = j
        m = min(m, j)
    return a

'다른 사람의 풀이1'과 완전히 같은 풀이로 도착점 기준으로 정렬한뒤 새로운 단속카메라를 추가해하는지 여부를 판단하는 방식이었습니다.🐧🐧🐧

감사합니다.