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

짱J·2023년 3월 6일
0

알고리즘 문제 풀이

목록 보기
24/30
post-thumbnail

문제 설명

구현 아이디어

문제 상황을 그대로 리스트나 큐로 구현하자 (나는 리스트를 선택하였다)
while문을 돌며 초마다의 상황을 리스트로 나타낸다.

  • 다리를 표현하는 리스트 bridge를 만든다
    • bridge의 길이 = bridge_length
  • 현재 bridge에 있는 트럭의 무게와 다음에 올라갈 트럭의 무게를 합쳤을 때, weight보다 작거나 같으면 다음 트럭을 bridge에 추가한다.
    • 그렇지 않다면 0을 추가한다. (bridge 리스트의 길이를 bridge_length로 유지하기 위해)
  • pop()을 통해 매 초마다 제일 앞에 있는 원소를 pop한다.
  • 모든 트럭이 다리를 지났으면, while문을 빠져나온다

전체 코드 1 - 시간 초과

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0] * bridge_length # 다리를 나타내는 리스트
    
    while bridge:
        answer += 1 # 1초씩 흐르는 것을 나타냄
        bridge.pop(0) # 다리의 가장 앞에 있는 원소를 pop
        
        if truck_weights:
            if sum(bridge) + truck_weights[0] <= weight:
                t = truck_weights.pop(0)
                bridge.append(t)
            else:
                bridge.append(0) # 리스트의 길이를 bridge_length로 유지하기 위해
            
    return answer

반복문마다 sum() 함수로 bridge에 있는 원소의 합을 계산해주기 때문에, 시간 초과가 발생하였다.

전체 코드 2 - 정답입니다

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0] * bridge_length
    total = 0
    
    while bridge:
        answer += 1
        total -= bridge.pop(0)
        
        if truck_weights:
            if total + truck_weights[0] <= weight:
                t = truck_weights.pop(0)
                bridge.append(t)
                total += t
            else:
                bridge.append(0)
            
    return answer

total이라는 변수를 만들어, pop이나 append되는 원소만 갱신하도록 코드를 수정하여 모든 테스트 케이스를 통과할 수 있었다.

profile
[~2023.04] 블로그 이전했습니다 ㅎㅎ https://leeeeeyeon-dev.tistory.com/

0개의 댓글