프로그래머스 | 스택, 큐 - 다리를 지나는 트럭 (python)

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

프로그래머스

 

🔅 문제 접근

FIFO으로, 큐 자료형태를 갖춘 형태로 다리를 건너기 때문에 큐 자료구조를 사용해서 문제를 풀면 될 것 같다는 생각이 들었다. 그리고 다리를 건너려면 다리 길이 만큼을 다리 위에서 머물러야 하기 때문에, 각 트럭이 잔여 거리를 튜플 형태로 가지고 있으면서 잔여거리가 0이 되면 다리에서 나오게 하는 방식으로 문제를 풀이하였다.

 

🔅 나의 풀이

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    Max = bridge_length * len(truck_weights) + 100
    truck_weights = deque(truck_weights)
    bridge = deque()
    current_weight = 0

    # 가능한 최대 시간인 Max값만큼 for문으로 순회
    for j in range(1,Max):
        d = -1
        # 다리 위의 모든 트럭에 대해 잔여거리 -1
        for i in range(len(bridge)):
            bridge[i][1] -=1
            # 잔여거리가 0인 트럭의 개수 카운트
            if bridge[i][1] == 0:
                current_weight -= bridge[i][0]
                d = i
        
        # 잔여거리가 0인 트럭의 개수만큼 pop left
        for i in range(d+1):
            if bridge:
                bridge.popleft()
        # 다리에 새로운 트럭 올리기 (weight를 넘지 않는다면)
        if truck_weights:
            if current_weight + truck_weights[0] <= weight and truck_weights:
                t = truck_weights.popleft()
                bridge.append([t, bridge_length])
                current_weight += t
        
        # 다리 위에 트럭이 없어지면 반복문 종료
        if len(bridge) == 0:
            answer = j
            break

    return answer

 

• 구조 : 각 트럭을 [트럭의 무게, 남은 거리] 형태의 리스트로 bridge deque에 저장하여 다리를 지나가는 트럭들을 관리한다.
• 과정:
  • for문으로 통해 매 시간마다 다리를 건너는 트럭들의 남은 거리를 감소시키고, 다리를 다 지난 트럭은 다리에서 제거해 current_weight에서 그 무게를 뺀다.
  • 대기 중인 트럭의 무게가 제한을 넘지 않으면 다리에 추가하고, 그렇지 않으면 다음 트럭이 대기하도록 한다.
  • 다리에 트럭이 남아 있지 않으면 현재 시점을 answer에 저장하고 반환한다.
• 아쉬운 점
  • 다리를 다 지난 트럭을 찾기 위해 매번 for 반복문을 실행하고, 특정 인덱스를 제거하는 부분이 비효율적이다. bridge의 길이가 길어질수록 성능 저하가 크게 발생할 수 있다

정답으로 처리되기는 하였으나, 상단의 이유로 그닥 만족스럽지는 않은 코드였다.

 

🔅 프로그래머스 풀이

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step

 

프로그래머스에서 좋아요를 많이 받은 코드를 분석해보겠다.

• 구조 : 다리 길이만큼 bridge를 0으로 초기화 해 트럭이 이동하는 과정을 deque의 큐 방식으로 구현한다.
• 과정 : 
  • 각 반복에서 가장 앞에 있는 요소를 popleft로 제거하며, 다리를 빠져나가는 트럭의 무게를 total_weight에서 차감한다.
  • 다리에 새로운 트럭이 진입 가능한지 확인해 bridge에 트럭을 추가하거나 0을 추가해 빈 공간으로 이동시킨다.
• 장점 : 
  • 내가 푼 풀이처럼 반복마다 전체를 검사하는 건이 아닌, 한 번의 무게 비교, popleft() 및 append()연산을 통해 효율적으로 다리를 건너는 트럭을 관리한다.
  • 맨 마지막 트럭이 다리에 올라간 뒤, 다리 길이만큼을 더해주는 방식으로 마지막 트럭이 다리를 완전히 지나가는 시간을 계산한다.

🔅 개선한 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque([0]*bridge_length)
    total_weight = 0
    step = 0
    truck_weights = deque(truck_weights)
    
    while truck_weights or total_weight > 0:
        step += 1
        # 다리를 빠져나간 트럭 무게 제거
        # 다리의 맨 왼쪽에 트럭이 없을 경우 값 변화 없음
        total_weight -= bridge.popleft()
        
        if truck_weights and total_weight + truck_weights[0] <= weight:
            truck = truck_weights.popleft()
            bridge.append(truck)
            total_weight += truck
        else:
            bridge.append(0)

    return step

 

 위와 같이 코드를 개선하였다. 다만 프로그래머스의 풀이에서는 truck_weights.reverse()로 리스트를 뒤집어 pop()을 사용했는데, 대신 deque의 popleft() 연산을 활용해서 보다 효율적으로 계산할 수 있게 하였다.

 또한, 프로그래머스 풀이에서는 whlie truck_weights로 트럭이 모두 다리를 건너기 전까지 반복한 뒤, 다리 길이 만큼을 추가하는 방식으로 연산하였으나 개선된 풀이에서는 while truck_weights or total_weight >0으로 다리 위 트럭의 총 무게가 0이 될 때까지 반복하도록 하여 코드의 간결성을 높였다.

🔅 배운점 및 느낀점

 문제를 풀때는 정말 적절한 자료구조 및 알고리즘을 선택하고, 해당 방식의 특성을 잘 살려서 풀이하는 것이 중요한 것 같다고 느꼈다.

나는 문제를 푸는 과정에서 queue를 사용하기는 하였으나, 결국 전체를 n번 순회하는 반복문을 순회함으로써 popleft 또는 append 시에 O(1)의 시간복잡도가 소요되는 queue의 장점을 전혀 살리지 못했다.

 

 앞으로 문제를 풀 때는, 하나의 풀이법만 생각하고 구성하기보다 일단은 브루트포스적인 풀이를 먼저 생각하더라도 (문제를 풀기는 풀어야하니.. ) 이외에 개선된 풀이도 여러개 생각하는 것이 중요할 것 같다. 특히, 문제를 풀 때 자료구조 및 알고리즘의 특성을 고려하여 여러 풀이를 떠올리고, 그 중에서 적합한 것을 선택하여 구현하는 연습을 많이 해야할 것 같다.

 

 그리고 이렇게 다양한 풀이 방식을 떠올리고, 무엇이 좋은지 판단하기 위해서는 정말 많은 연습이 필요하겠지. 짧은 시간 안에 되는 것은 아니겠지만, 매일 완벽하게 문제를 풀겠다라는 마음보다 조금씩 배워나간다라는 마음으로 꾸준히 노력해야겠다. 화이팅 !!