[프로그래머스] 다리를 지나는 트럭 (Level 2) (파이썬 python)

 

 

문제 링크

 

 

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

코딩테스트 연습 - 다리를 지나는 트럭

 

 

문제

 

 

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다.

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다.

다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다.

단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다.

무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

 

 

경과 시간다리를 지난 트럭 / 다리를 건너는 트럭 / 대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

 

 

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length,

다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다.

이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

 

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

 

bridge_length / weight / truck_weights / return

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

 

 

문제 풀이

 

 

# 나의 풀이

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0] * bridge_length
    while bridge:
        answer += 1
        bridge.pop(0)
        if truck_weights and truck_weights[0] + sum(bridge) <= weight:
            bridge.append(truck_weights.pop(0))
        else:
            if truck_weights:
                bridge.append(0)
    return answer

 

 

bridge를 입력받은 최대 트럭의 개수만큼 0을 넣어 초기화시켜준다.

이 bridge는 현재 다리를 지나는 트럭의 배열이다.

1초 마다 bridge의 배열을 하나씩 pop시켜주어 하나씩 순서대로 다리를 나가도록 해준다.

조건문을 사용하여, 만약, 다리에 넣어줄 truck_weights의 첫 번째 원소와

현재 다리에 있는 트럭들의 무게의 합이 최대 무게 이하일 경우

bridge에 truck_weights의 첫 번째 원소를 넣어주고,

최대 무게보다 클 경우 0을 넣어준다.

이렇게 bridge의 길이는 유지시켜주어, 시간의 관리를 쉽게 해준다.

if문에 들어있는 truck_weights가 사실 조건문 밖에서 if truck_weights로 공통으로 적용되게 해놓았었는데,

이렇게 했더니 시간 초과가 났었다.

찾아보니 sum의 시간 복잡도가 O(N)으로 큰데, 아마 이중 조건문으로 인해 반복되어 그런 것 같았다.

그래서 각 조건문으로 sum을 빼주었더니 테스트 케이스를 통과했다.

그런데 약간 찝찌입-한 마음이 생겼다 ...

그래서 sum을 안쓸 수 있는 다른 분의 풀이를 찾아봤다

 

 

# 다른 사람의 풀이

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

 

이 풀이에서는 deque를 사용했다.

deque를 사용할 경우 pop(0) (시간복잡도 O(N))을 popleft() (시간복잡도 O(1))로 대체 가능하기 때문에 유리하다.

이 분은 아예 truck_weights를 처음부터 reverse()로 뒤집어서 pop으로 빼주셨다

 그리고 sum을 사용하지 않고 처음에 total_weight라는 0으로 초기화된 변수를 사용하여 검사해주었다.

total_weight에 다리 위에 올라오는 truck의 무게를 더해주고

나가는 트럭에 대해서는 무게를 빼주는 것이다.

이렇게 되면 새로 들어올 것과 기존 무게를 더하여 검사할 때에도 sum 함수가 쓰이지 않고

변수 하나만 들어가므로 시간 복잡도가 줄어든다!