[programmers]Python_다리를 지나는 트럭

문제

 

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 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 이하입니다.

 

코드

 

class 사용하지않은 코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    n = len(truck_weights) #현재 트럭 수
    time = 0
    
    pass_truck = [] #지나간 트럭
    move_truck = deque([]) #지나는 트럭
    truck_weights = deque(truck_weights) #deque형식으로 변환
    
    while len(pass_truck) < n:
        #다리를 1씩 이동하면서 지나갔는지 안지나갔는지 판단
        trucks = move_truck
        move_truck = deque([])
        while trucks:
            truck, loc = trucks.popleft()
            if loc + 1 > bridge_length:
                pass_truck.append(truck)
            else:
                move_truck.append([truck, loc + 1])
        
        #대기하고있는 트럭이 있으면 pop
        if truck_weights:
            cur_truck = truck_weights.popleft()
            
        #다음 트럭이 올라가도 다리가 버틸 수 있다면 추가
        if sum([truck[0] for truck in move_truck]) + cur_truck <= weight:
            move_truck.append([cur_truck, 1])
        #못 버틴다면 다시 대기
        else:
            truck_weights.appendleft(cur_truck)
        time += 1
        
    return time

 

class 사용한 코드

#다른 사람의 풀이
from collections import deque

DUMMY_TRUCK = 0

class Bridge(object):
	#초기화
    def __init__(self, length, weight):
        self._max_length = length #다리의 길이 정의
        self._max_weight = weight #다리가 버틸 수 있는 무게 정의
        self._queue = deque([]) #다리에 올라가있는 트럭
        self._current_weight = 0 #현재 다리 위에 있는 트럭 무게 합

    def push(self, truck):
        next_weight = self._current_weight + truck #다음 트럭이 올라갔을때 무게
        #무게가 버틸 수 있는지, 트럭이 더 올라갈 수 있는지 확인
        if next_weight <= self._max_weight and len(self._queue) < self._max_length:
            self._queue.append(truck) 
            self._current_weight = next_weight
            return True
        else:
            return False

    def pop(self):
        item = self._queue.popleft() #아직 트럭이 올라가있다면 pop
        self._current_weight -= item #지나간 트럭의 무게만큼 빼준다
        return item

    def __len__(self):
        return len(self._queue)

    def __repr__(self):
        return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue))


def solution(bridge_length, weight, truck_weights):
    bridge = Bridge(bridge_length, weight) #다리 인스턴스 생성
    trucks = deque(truck_weights)
	
    #truck 수만큼 0을 추가해준다
    for _ in range(bridge_length):
        bridge.push(DUMMY_TRUCK)

    count = 0
    #대기하고 있는 트럭이 있는동안 반복
    while trucks:
    	#다리 위에 트럭이 올라갈 자리를 만든다
        bridge.pop()
		
        #첫 번째 트럭이 올라갈 수 있는 조건에 만족한다면 올라간다
        if bridge.push(trucks[0]):
            trucks.popleft()
        #조건에 만족하지 못하면 다시 대기한다
        else:
            bridge.push(DUMMY_TRUCK)

        count += 1
	
    #아직 다리 위에 트럭이 있다면 1씩 이동하면서 지나가게한다
    while bridge:
        bridge.pop()
        count += 1

    return count

 

진행 과정

 

예제 #1

bridge_length = 2

weight = 10

truck_weights = [7,4,5,6]

 

위에서 class를 사용한 코드와 그렇지 않은 코드로 나눈 이유는 시간복잡도에 많은 차이가 나타났기 때문이다. 물론 class를 사용한 코드가 더 빠르다.

 

일단 트럭이 다리 위에 올라갈 수 있는 조건은 다리가 버틸 수 있는 무게 > 현재 올라가있는 트럭의 무게 + 올라갈 트럭의 무게, 다리의 길이 >= 현재 올라가있는 트럭 수 + 1 이다.

 

순서는 직관적으로 생각하면된다. 대기하고 있는 첫 번째 트럭이 다리 위로 올라가고 다음 time에 그 다음 대기하고 있던 트럭이 올라갈 수 있는지 없는지를 조건으로 확인하고 올라가든지 더 대기하든지 한다. 동시에 다리의 길이 1씩 이동한다.

 

class를 사용한 코드에서는 이 과정을

 

bridge.pop()

if bridge.push(trucks[0]):

    trucks.popleft()

else:

    bridge.push(DUMMY_TRUCK)

count += 1

 

로 구현되었다.

 

1씩 이동한 것은 bridge.pop()이라고 보면 되고 push()를 실행하면서 조건에 맞는지 안맞는지 판단한다음 올라갈지 대기할지 진행한다. 그리고 count + 1을 해주는데 count를 경과 시간으로 보면 된다.

 

이후에 대기하고 있는 트럭이 더 이상 없고 아직 다리 위에 트럭이 있을때

 

while bridge:

    bridge.pop()

    count += 1

 

로 구현되어 그냥 조건 확인없이 1씩 이동해주면 된다.

 

class를 사용하지 않은 코드는 내가 작성했지만 굉장히 더럽고 효율적이라서 설명하진않겠다. 주석으로 간단히 적어놨으니...

 

코드 진행 과정은 __repr__을 실행하여 확인해볼 수 있다.

 

1) Bridge(7/10 : [[0, 7]]) # 현재 올라가있는 트럭의 무게 합 / 다리가 버틸 수 있는 무게 : 다리 위에 있는 트럭 현황
2) Bridge(7/10 : [[7, 0]])
3) Bridge(4/10 : [[0, 4]])
4) Bridge(9/10 : [[4, 5]])
5) Bridge(5/10 : [[5, 0]])
6) Bridge(6/10 : [[0, 6]])