프로그래머스 - 다리를 지나는 트럭 / 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_lengthweighttruck_weightsreturn

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 for _ in range(bridge_length)]
    total = 0  # sum(bridge) 시간초과 대비용 변수

    while total != 0 or len(truck_weights) > 0:  # 다리에 트럭이 없고, 모든 트럭이 지날 때 까지 반복
        total -= bridge.pop(0)  # 맨 앞 트럭 통과, 다리 적재량 감소
        if truck_weights and total + truck_weights[0] <= weight:  # 다음 트럭의 무게를 버틸 수 있으면 통과
            truck = truck_weights.pop(0)  # 다음에 통과할 트럭
            total += truck  # 다리 적재량 중가
            bridge.append(truck)  # 다리에 다음 트럭 진입
        else:
            bridge.append(0)
        answer += 1  # 1초 증가

    return answer

---

풀이

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0 for _ in range(bridge_length)]
    total = 0  # sum(bridge) 시간초과 대비용 변수

    while total != 0 or len(truck_weights) > 0:  # 다리에 트럭이 없고, 모든 트럭이 지날 때 까지 반복
        total -= bridge.pop(0)  # 맨 앞 트럭 통과, 다리 적재량 감소
        if truck_weights and total + truck_weights[0] <= weight:  # 다음 트럭의 무게를 버틸 수 있으면 통과
            truck = truck_weights.pop(0)  # 다음에 통과할 트럭
            total += truck  # 다리 적재량 중가
            bridge.append(truck)  # 다리에 다음 트럭 진입
        else:
            bridge.append(0)
        answer += 1  # 1초 증가

    return answer

  다리 전체를 하나의 큐로 만들어 트럭을 지나게하는 문제입니다. 다리에 트럭이 없고, 모든 트럭이 지날 때까지 1초씩 증가시킵니다. 

 total 대신 sum(bridge)를 사용하게 되면 매번 반복 때마다 sum()을 계산하여 시간 초과가 나므로 주의해야 합니다.