# 테페리넷

## 테페리넷

### 관리자 전용

ps:problems:programmers:42583

# 다리를 지나는 트럭

ps
링크https://programmers.co.kr/learn/courses/30/lessons/42583
출처프로그래머스
문제 번호42583
문제명다리를 지나는 트럭
레벨Level 2
분류

시간복잡도O(n)
인풋사이즈n<=10000
사용한 언어Python
해결날짜2021/05/21
태그

## 풀이

• 다리 위에 있는 트럭들을 큐로 관리해주면 쉽게 처리되는 문제이다.
• 그것을 나이브하게 풀면, 매 초마다 새 트럭이 다리에 올라갈수 없는 경우에 무게 0짜리의 가상 트럭을 대신 다리에 올리는 것처럼 구현할 수 있고, 이 경우에는 전체 걸린 시간, 즉 O(n*m)에 풀린다 (n=트럭의 갯수, m=다리의 길이). 비효율적이지만, 정답에 올라가있는 대부분의 코드가 이러한 방식으로 구현되어있다. (코드 1)
• 트럭마다 트럭의 무게와 다리에 올라간 시간을 함께 묶어서 큐에 저장하면, 가상 트럭 없이 실제 트럭들에 대해서만 큐에 한번씩만 추가/삭제하는 것으로 전체 걸린 시간을 계산할 수 있다. 이렇게 하면 O(n)에 해결 가능하다. (코드2)

## 코드

### 코드 1 - O(n*m)

"""Solution code for "Programmers 42583. 다리를 지나는 트럭".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42583
- Solution link: http://www.teferi.net/ps/problems/programmers/42583
"""

import collections

def solution(bridge_length, weight, truck_weights):
weight_sum = 0
trucks_on_bridge = collections.deque( * bridge_length)
sec = 0
for truck_weight in truck_weights:
while True:
sec += 1
weight_sum -= trucks_on_bridge.popleft()
if weight_sum + truck_weight <= weight:
trucks_on_bridge.append(truck_weight)
weight_sum += truck_weight
break
trucks_on_bridge.append(0)
return sec + bridge_length

### 코드 2 - O(n)

"""Solution code for "Programmers 42583. 다리를 지나는 트럭".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42583
- Solution link: http://www.teferi.net/ps/problems/programmers/42583
"""

import collections

Truck = collections.namedtuple('Truck', ['weight', 'enter_time'])

def solution(bridge_length, weight, truck_weights):
weight_sum = 0
trucks_on_bridge = collections.deque()
cur_sec = 0
for cur_truck_weight in truck_weights:
cur_sec += 1
if (trucks_on_bridge and
trucks_on_bridge.enter_time + bridge_length <= cur_sec):
weight_sum -= trucks_on_bridge.popleft().weight
while weight_sum + cur_truck_weight > weight:
out_truck = trucks_on_bridge.popleft()
cur_sec = out_truck.enter_time + bridge_length
weight_sum -= out_truck.weight
trucks_on_bridge.append(Truck(cur_truck_weight, cur_sec))
weight_sum += cur_truck_weight
return cur_sec + bridge_length

## 토론

댓글을 입력하세요:
U﻿ J P G D

ps/problems/programmers/42583.txt · 마지막으로 수정됨: 2021/05/21 07:16 저자 teferi

### 문서 도구 