세무민의 코딩일기 : 프로그래머스 다리를 지나는 트럭 문제 풀기

이번 문제는 다리를 지나는 트럭 문제!

이 문제는 기존에 Stack이나 Queue를 이용해서 문제를 푸는 걸 추천하지만 

나는 list로 구현했당....

사실 deque으로 구현했던 건 있으나 코드 실행은 문제 없지만 채점에서 실패한 것들이 존재해서..ㅎ

그냥 무난한 리스트로 ㅎ

---

문제 설명

 

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다.

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며,

다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.

※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다.

무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수는 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights

이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

---

제한 조건 및 입출력 예시

---

풀이 

이번 문제에서 핵심 포인트는 다리를 지난 트럭들은 삭제하는 것이 중요!

Deque을 사용하든 List를 사용하던 무관하지만 결국에는 While로 반복하여 Count의 수를 증가해야 하기 때문에 

기존 Truck_Weights를 잘 이용하는 것이 중요한 포인트!

위에 3번째 예시를 기반으로 확인해보자 

우선 다리 길이가 100으로 100칸을 움직일 수 있으며 100칸의 길이에 트럭들을 이동시킬 수 있다.

위에 그러면 무계가 10인 트럭 10개는 한번에 옮길 수 있기 때문에 

110개가 나오게 된다. 

식으로 표현하자면  sum(frontTruckWeights) + truck_Weights[0]  <= weight 

위에 기준이 통과 된다면 트럭 리스트에서 하나씩 빼주면 끝!

---

코드

from collections import deque

def solution(bridge_length, weight, truck_weights):

    bride = [0] * bridge_length
    count = 0 
    maxSize = 0
    while len(bride) > 0:
        count += 1
        maxText = bride.pop(0)
        if maxText != 0:
            maxSize -= maxText
        if len(truck_weights) != 0:
            if maxSize + truck_weights[0] <= weight:
                tmp = truck_weights.pop(0)
                maxSize += tmp
                bride.append(tmp)
            else:
                bride.append(0)



    return count

우선 길이만큼 배열의 크기를 만들어 준다. 

위에 예시를 기반으로 말하자면 

내가 10을 추가했을 때 길이가 100이라서 결국에 101번째가 되야 bride는 빈 리스트가 되기 때문에 

길이만큼 리스트를 만들어 준 후 count를 1씩 증가해주면 된다. 

 MaxSize는 위에 sum(frontTruckWeights)를 구현하기 위해 만든것!

그리고 bride 리스트에서 하나씩 뺄때 그 값이 0이 아니라면 트럭이라는 의미를 가지도록 만들었는데 

트럭이라는 값이 빠지게 된다면 maxSize를 해당 값만 큼 빼주면 된다.

그리고 sum한 값과 첫번째 트럭값의 크기가 Weight보다 작다면 

트럭을 하나 빼서 bride에 넣어주면 끝!

이때 maxSize는 방금 뺀 트럭의 크기를 추가해주면 끝!

끄읕!

---

처음에 deque으로 풀었다가 

잘 안되서 리스트로 구현했더니 좀 편하게 만들었다.

무튼 다음에도 더 알찬 포스팅으로 찾아오겠습니다.