[프로그래머스] 다리를 지나는 트럭 Python 풀이

📘 문제

플랫폼: 프로그래머스
난이도: Lv2
유형: 큐, 시뮬레이션

 

🔗 문제 링크

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

프로그래머스

 

매개변수로 주어지는 truck_weights 배열은 트럭의 무게가 나열된 배열이다.

이 트럭들이 weight(매개변수)만큼 버티는 다리를 무사히 지나갈 수 있는 최소 시간을 구하는 문제이다.

그리고 다리엔 최대 bridge_length(매개변수)개의 트럭이 올라갈 수 있다. (= 다리 길이인듯?)

 

 

🧠 접근 방법 및 풀이 과정

 

처음엔 문제에 나와있는대로 시뮬레이션 돌려서 풀었는데 63% 맞았다 ㅠ,ㅠ

 

그래도 설명해보자면 1초부터 시작해서 다리, 대기줄, 건너간 트럭 총 3개의 que를 만들고

건너간 트럭 큐의 길이와 처음 대기줄의 길이가 같아질 때까지 문제에 나와있는대로 시뮬레이션을 돌리며

time을 1씩 더해간다.

 

처음 코드

from collections import deque

def cal_bridge_weight(arr, new, w):
    total = 0
    
    for v in arr:
        total += v
    
    return total + new <= w

def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    bridge = deque()
    waiting_que = deque(truck_weights)
    complete = deque()
    origin_length = len(truck_weights)
    
    time = 1
    
    while len(complete) != origin_length:
        time += 1
        
        if bridge:
            if len(bridge) < bridge_length:
                bridge.append(0)
            if len(bridge) == bridge_length:
                temp = bridge.popleft()
                if not temp == 0:
                    complete.append(temp)
        
        if waiting_que:
            cur_truck = waiting_que.popleft()
            
            if len(bridge) < bridge_length and cal_bridge_weight(bridge, cur_truck, weight):
                bridge.append(cur_truck)
            else:
                waiting_que.appendleft(cur_truck)
    
    return time

 

몇 분간 고민해본 결과 다리를 건너는 로직이 잘못된 것 같다는 생각이 들었다.

처음 코드의 경우 다리에 해당하는 que에 시간의 흐름에 따라 새로운 트럭을 넣거나 0을 넣어서 다리를 건너는 시간을 처리 했는데

다리에 트럭이 진입하면서부터 시간을 넣어서 시간이 다되면 다리를 빠져나가는 로직으로 수정하게 됐다.

 

사실 이 방법을 생각하지 않은 건 아니었지만 구현이 잘 안돼서 포기했었다 ㅠㅠ

하지만 아무리 생각해봐도 이걸(다리 건너는 시간 계산) 수정하면 문제가 풀릴 것 같아서

열심히 머리를 굴리며 구현해보았다.

 

최종 코드는 아래와 같다!

 

💻 코드 & 설명

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    bridge = deque()
    waiting = deque(truck_weights)
    total_weight = 0

    while waiting or bridge:
        time += 1

        # 1. 시간이 된 트럭 제거
        if bridge and time - bridge[0][1] >= bridge_length:
            out_truck = bridge.popleft()
            total_weight -= out_truck[0]

        # 2. 다음 트럭 추가
        if waiting and total_weight + waiting[0] <= weight:
            truck = waiting.popleft()
            bridge.append((truck, time))  # (무게, 들어간 시간)
            total_weight += truck

    return time

 

 

✨ 회고 / 느낀 점

이런 문제를 JAVA로 풀 땐 class를 만들어서 자주 풀었는데

갑자기 python으로 풀려고 하니까 튜플이나 배열로 무게랑 시간 정보를 둘다 저장하면 되는걸

큐에 값 1개만 들어가야 한다는 것에 집착(?)해서 풀기 더 어려웠따

 

💭 다른 사람의 풀이에서 JAVA처럼 클래스를 만들어서 푼 풀이가 있었다.

다음엔 나도 저렇게 풀어봐지