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

입력은 3개가 주어진다.

 

bridge_length : 다리에 올라갈 수 있는 트럭 수

weight : 다리가 견딜 수 있는 무게 

truck_weights : 트럭별 무게

 

문제는 '모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는가?'이다.

 

아래처럼 이해하면 편하다.

bridge_length는 다리의 길이이다. 다리의 길이가 N이라면, N대가 올라갈 수 있다.

그리고 1대만 지나가는데 N초가 걸린다.

 

그리고 다리에서 완전히 나가야지 건넜다고 할 수 있다.

 

[7, 4, 5, 6]를 스택형태로 이동시켜보자.

 

 

0 : [x,x] [] (시작)
1 : [x,7] []
2 : [7,x] []
3 :[x,4] [7]
4 : [4,5] [7]
5 : [5,x] [4,7]
6 : [x,6] [5,4,7]
7 : [6,x] [5,4,7]
8 : [x,x] [6,5,4,7]

 

 

이 문제는 고민을 많이 했음에도 풀지 못했다.

다른 사람 풀이를 보며 이해해보자. 출처

 

 

def solution(bridge_length, weight, truck_weights):

    answer = 0

    trucks_on_bridge = [0] * bridge_length

    while len(trucks_on_bridge):  # 자동차를 모두 지나가게 할 때까지
        answer += 1
        trucks_on_bridge.pop(0)

        if truck_weights:  # 자동차가 남아있다면
            if sum(trucks_on_bridge) + truck_weights[0] <= weight:  # 자동차 무게가 초과하지 않으면
                trucks_on_bridge.append(truck_weights.pop(0))  # 길 위에 자동차 추가하기
            else:
                trucks_on_bridge.append(0)
    return answer


print(solution(2, 10, [7, 4, 5, 6]))

 

 

코드를 조금 수정해봤다.

 

 

from collections import deque


def solution(bridge_length, weight, truck_weights):

    answer = 0
    hap = 0

    truck_weights = deque(truck_weights)
    trucks_on_bridge = deque([0] * bridge_length)

    while trucks_on_bridge:  # 자동차를 모두 지나가게 할 때까지
        answer += 1

        w = trucks_on_bridge.popleft()
        hap -= w

        if truck_weights:  # 자동차가 남아있다면
            if hap + truck_weights[0] <= weight:  # 자동차 무게가 초과하지 않으면
                w = truck_weights.popleft()
                trucks_on_bridge.append(w)  # 길 위에 자동차 추가하기
                hap += w

            else:
                trucks_on_bridge.append(0)
    return answer


print(solution(2, 10, [7, 4, 5, 6]))

 

 

1. sum을 사용하지 않고, hap이라는 변수를 만들어서 값을 누적시켰다.

2. list에서 .pop(0)을 사용하면 가장 앞에 있는 원소가 빠지게 돼서 값들이 앞으로 당겨진다. 

이 과정을 없애기 위해 deque를 사용했다.

 

아래 시간을 비교해보면 확실히 빨라졌다.

 

 

다른 사람 풀이

 

 

수정한 풀이

 

 

 

이제 내 코드의 문제점을 파악해보자.

 

 

from collections import deque


def solution(bridge_length, weight, truck_weights):
    in_car = deque([0] * bridge_length)  # 길

    hap = 0  # 자동차 무게 합

    in_cnt = bridge_length  # 들어갈 수 있는 자동차 수
    start_cnt = 0  # 출발한 자동차 수

    l = len(truck_weights)

    answer = 0

    while start_cnt != l:

        tmp = truck_weights[0]
        while hap + tmp <= weight and in_cnt:  # 1.무게 초과 x 2. 들어갈 자리 o

            car = truck_weights.pop(0)
            in_car[0] = car  # 자동차 삽입
            print(in_car)

            in_car.rotate(1)  # 자동차 이동
            print(in_car)

            in_cnt -= 1
            start_cnt += 1
            hap += car

        if in_car[-1]:  # 자동차 내보내기
            in_cnt += 1
            hap -= in_car[-1]

            in_car[-1] = 0
            print(in_car)

            in_car.rotate(1)  # 자동차 이동
            print(in_car)

    return answer


print(solution(2, 10, [7, 4, 5, 6]))

 

 

Deque를 사용했지만, Rotate하려고 하니까 복잡해졌다. Stack 구조를 이용해야 했다.