0308_프로그래머스 : 다리를 지나는 트럭(deque, queue)

블로그 오랜만ㅎㅎ 3일만에 돌아왔다. 

이번에 도전한 문제는 프로그래머스의 다리를 지나는 트럭이다. 이거 해결하는데 꼬박 하루는 걸린 거 같다.

이 문제는 큐로 풀어야 하기 때문에 리스트 형태에서 pop(0)을 사용하는 것은 비효율적이라는 말을 들었다. 그래서 덱 구조를 사용해보았는데, 테스트케이스 10개 중 1개가 자꾸 시간초과가 뜨는 거다...하하

결국 시영쌤의 도움을 받아 간신히 극복했다. 항상 감사합니다 쌤

 

 

그럼 우선 푼 코드 공유

 

from collections import deque
 
def solution(bridge_length, weight, truck_weights):
    answer = bridge_length
    d = deque(truck_weights)
    passing = deque()
    passing_sum = 0
 
    while d:
        truck = d.popleft()
# 다리를 다 지난 트럭 빼기
        if len(passing) == bridge_length:
            tmp = passing.popleft()
            passing_sum -= tmp
# 시간 재기
        if passing_sum + truck <= weight:
            passing.append(truck)
            passing_sum += truck
            answer += 1
        else:
            passing.append(0)
            answer += 1
            d.appendleft(truck)
 
    return answer

 

[해결 로직]

 

- deque 구조로 바꿔주고 truck_weights가 비어있을 때까지 while 반복문을 돌렸다. 즉 트럭들이 다리를 모두 건너면 멈춘다.

- passing 에는 다리를 건너는 트럭, passing_sum은 다리를 건너는 트럭의 무게합을 할당

- 시간을 재는 조건문에서 다리 위의 모든 트럭의 무게와 새로 가져온 트럭의 무게 합이 주어진 weight 보다 작거나 같은 경우에만 다리 위에 새로 가져온 트럭을 올려준다. ( + 시간 1씩 증가 )

- 그러나 weight 를 초과하면 다리 위에 다음 트럭을 올리지 않고 대신 그 자리를 0으로 채워준다. ( 이때도 시간은 +1씩 증가 )

- 첫번째 조건문을 통해 다리를 모두 지난 트럭은 빼준다. passing에서 해당 트럭 popleft로 빼주고 passing_sum에서도 동일하게 빼주기

 

[보완점]

 

- deque구조를 처음 써봤는데 stack과 queue를 모두 사용할 수 있는 것이 특징이라고 함

- 처음에 시간초과 났던 이유는 다음과 같다. 두 번째 조건문에서 sum_passing이라는 변수를 사용하기 전에 sum(passing) 값으로 비교를 했는데, 그렇게 되면 passing에 원소 하나가 추가 또는 삭제(업데이트) 될 때마다 계산을 처음부터 끝까지 다시 해야 하기 때문에 시간이 오래 걸렸다고 한다. 그래서 passing이라는 변수를 만들어 해당 원소만 추가 또는 빼주는 형태로 코드 변경해 통과할 수 있었다.

- sum때문에 시간초과가 뜰 거라고는 생각 못했는데, 아무래도 내장함수에 대한 기본적인 이해가 부족해서일 것이다. (라는 피드백을 받았는데 무척이나 공감이 된다 ㅠㅎ)

 

 

 

 

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스