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

프로그래머스 '다리를 지나는 트럭' 문제 풀이입니다.

 

문제 링크

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

● 문제 간단 설명

다리를 지나는 순서와 무게가 정해져 있는 트럭 배열에 대해서 다리의 무게 한도를 넘지 않는 선에서 모든 트럭이 다리를 지나게 되는 시간을 구하는 문제

 

● 문제 해결 방향

다리를 지나는 순서가 정해져 있어서 고민할 부분이 적은 문제였던 것 같다.

 

문제에서 정의한 대로

시간을 1씩 증가시키면서

다리에 차가 없을 경우나 다리의 무게 한도에 가능한 트럭일 경우 트럭을 올리도록 하였다.

올림과 동시에 트럭이 다리를 통과하는 시간을 구하여 따로 배열을 만들어 저장하였다.

 

트럭이 다리에서 내릴 경우 동일하게 배열에서 값을 제거해주었다.

 

마지막 트럭이 다리에 오를 때, 다리를 통과하는 시간을 구할 수 있고,

그때 값을 return 해주었다.

 

● 문제 해결 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    now = []
    popTime = []
    
    time = 0
    while truck_weights:
        time += 1
        if now == [] :
            now.append(truck_weights.pop(0))
            popTime.append(time + bridge_length - 1)
        else :
            if sum(now) + truck_weights[0] <= weight:
                now.append(truck_weights.pop(0))
                popTime.append(time + bridge_length - 1)
            if time == popTime[0]:
                now.pop(0)
                popTime.pop(0)

    return popTime[-1] + 1

truck_weight 배열의 트럭이 모두 다리에 오를 때까지 반복해주었다.

 

시간을 1씩 추가하면서 경우에 따라 다른 처리를 해주었다.

우선 다리에 트럭이 업을 경우에는 다음 순서의 트럭을 다리에 올렸고, 다리에서 내리는 시간을 구해서 popTime 배열에 저장해주었다.

 

다리에 트럭이 있을 경우,

현재 다리에 올라와있는 트럭의 무게가 무게 한도보다 작으면 다리에 올려주었다.

그리고 현재 시간과 popTime의 0번째 값과 비교하여 다리에서 내릴 시간이 되면 now와 popTime 배열에서 값을 제거해주었다.

 

그리고 다리에 마지막 트럭이 오르는 순간 반복문이 멈추게 된다.

popTime의 -1 번째 index에 마지막 트럭이 다리에서 내리는 시간이 저장되어 있기 때문에 popTime [-1] + 1을 return 한다.

( popTime의 값이 다리에 있을 수 있는 마지막 초를 의미하기 때문에 다리를 최종적으로 다 건너는 시간은 +1 해주어야 한다. )

 

여기서 deque 라이브러리를 사용해주었는데,

기존 배열을 사용하여 pop을 사용했을 때 보다 약간의 시간적 이득을 볼 수 있었다.

 

다른 문제 풀이들을 보면서

스택/큐 문제에서 유용하게 사용할 수 있는 라이브러리를 찾을 수 있었다.

deque라는 라이브러리인데, 양방향 큐를 사용할 수 있는 라이브러리라고 한다.

 

일반적인 리스트의 경우 pop, append의 연산이 O(n)의 시간 복잡도를 가지는데,

deque의 경우 O(1)의 시간 복잡도로 동일한 연산이 가능하다고 한다.

 

간단한 사용법

from collections import deque

arr = deque()

# 오른쪽에 끝에 값 추가
arr.append(10)

# 왼쪽에 끝에 값 추가
arr.appendleft(10)

# 오른쪽 끝 값을 가져오는 동시에 제거
arr.pop()

# 왼쪽 끝 값을 가져오는 동시에 제거
arr.popleft()

# 인자 배열을 순회하면서 오른쪽 끝에 값 추가
arr.extend([1, 2, 3])

# 인자 배열을 순회하면서 왼쪽 끝에 값 추가
arr.extendleft([1, 2, 3])

# 값을 deque에서 찾아서 제거
arr.remove(10)

# 인자의 숫자 값 만큼 회전 ( 음수 - 왼쪽, 양수 - 오른쪽 )
arr.rotate(4)
arr.rotate(-2)

 

 

● 참고

Python - 데크(deque) 언제, 왜 사용해야 하는가?