[프로그래머스] Level 2_다리를 지나는 트럭(스택/큐)

문제 유형

스택/큐

 

문제

프로그래머스

 

나의 문제풀이

1차(시간초과)

def solution(bridge_length, weight, truck_weights):
    answer = 0
    passing_truck = 0
    
    while len(truck_weights) > 0:
        # 한 다리에 지나간 트럭의 개수
        pass_truck = truck_weights.pop(0)
        
        weight -= pass_truck
        answer += bridge_length
        
        for i in range(len(truck_weights)):
            weight -= truck_weights[i]
            if weight < 0:
                passing_truck = i
                break
        # for문 다 통과한 경우 고려하기
        
        if passing_truck > 0:
            answer += passing_truck
            truck_weights = truck_weights[passing_truck:]
        elif passing_truck == 0 and weight > 0:
            answer += len(truck_weights)
        
    return answer

 

2차(다른 사람의 문제풀이)

• bridge에 다리 지나가는 형상을 만들어놓기(다리 길이와 같은 길이의 값이 0으로 된 리스트 생성)
• bridge에 1초에 한 번씩 값 나오기
• truck_weights[0]의 값이 weight보다 작으면 bridge 지나가기, weight보다 크면 0 넣고 트럭 지나가지 않음
• truck_weights 길이가 0이면 if truck_weights 종료
• bridge 길이가 0이면 while문 종료 후 answer 리턴

def solution(bridge_length, weight, truck_weights):
    
    answer = 0
    bridge = [0 for _ in range(bridge_length)]
    
    while bridge:
        
        answer += 1
        bridge.pop(0)
        
        if truck_weights:
            if sum(bridge) + truck_weights[0] <= weight:            
                t = truck_weights.pop(0)
                bridge.append(t)
            else:
                bridge.append(0)
                
    return answer

 

리뷰

- 며칠동안 고민했는데 답이 안나와서 다른 사람의 풀이 참고

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

- deque 사용하면 시간초과 오류 -> 문제마다 list, deque 사용 시간이 다를 수 있음!(보통은 deque가 더 빠름)

다리를 지나는 트럭 python 프로그래머스

- 다리 길이를 리스트로 활용 -> 직접 트럭이 지나가는 것처럼 구현하기!