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

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

프로그래머스

문제 개요

[input]
bridge_length: 트럭 수
weight: 다리가 견딜 수 있는 무게
truck_weights: 트럭 별 무게

[return]
모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지

 

나의 코드

def solution(bridge_length, weight, truck_weights):
    answer = 0
    road = [0]*bridge_length
    x = truck_weights.pop(0)
    sum_weight = 0 

    while len(truck_weights)>=0:
        sum_weight-=road[0]
        road.pop(0)
        road.append(0)
        if sum_weight+x <= weight:
            road[-1]=x
            sum_weight+=x
            answer+=1
            if len(truck_weights)>0:
                x = truck_weights.pop(0)
            else:
                answer+=bridge_length
                break

        else:
            answer+=1

    return answer

• 시간초과 문제
  • sum 함수가 시간초과 요인임! : 
    sum_weights=0 한 후
    루프 돌 때마다 weight을 -+= 하는 게 훨씬 좋음.
  • 리스트의 맨 처음 원소를 pop하고 싶을 때, pop(0)은 시간초과 가능하므로
    아래 두 가지 대안
    1) .popleft()
    2) truck_weights.reverse() 이후 .pop()
• TypeError: 'NoneType' object is not subscriptable
  - 코랩에서 if문에 화살표 가리키더라도,  첫 코드부터 혹은 그 코드자체가 처음부터 틀렸다는 게 아니라,
    여러 번 루프 돌린 후 해당 if문에 문제가 생겼다는 거
  - 문제의 코드: road = road[1:].append(0) 
     → None을 반환함, road[1:] 처리 후, 다음 줄에서 append. 따로 실행해야 함 (최종 코드에는 아예 pop(0)으로 대체)
  - 본 에러메시지는, 주로 리스트가 비어있는데 index에 접근하는 등, 빈 리스트에 특정 처리를 하면 발생.

 

모범 코드

1. 리스트.reverse 이후 pop() & deque 함수 사

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

2. 간결함

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

*sum 함수 수정 필요

• "while 변수: "
  0이나 null값일 경우 False이기때문에, 빈리스트가 아니라면 True가되어 실행되는 함수
  ex) while truck_weights: / while q: