규도자 개발 블로그

[프로그래머스/Level2/파이썬3(python3)] 다리를 지나는 트럭 본문

알고리즘/풀이

[프로그래머스/Level2/파이썬3(python3)] 다리를 지나는 트럭

규도자 (gyudoza) 2021. 3. 11. 10:27

[프로그래머스/Level2/파이썬3(python3)] 다리를 지나는 트럭

문제

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.


경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭
0[][][7,4,5,6]
1~2[][7][4,5,6]
3[7][4][5,6]
4[7][4,5][6]
5[7,4][5][6]
6~7[7,4,5][6][]
8[7,4,5,6][][]

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

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한사항

  • bridge_length는 1 이상 10,000 이하입니다.
  • weight는 1 이상 10,000 이하입니다.
  • truck_weights의 길이는 1 이상 10,000 이하입니다.
  • 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_lengthweighttruck_weightsreturn
210[7,4,5,6]8
100100[10]101
100100[10,10,10,10,10,10,10,10,10,10]110

풀이

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

설명

이런 문제를 보면 항상 코드로 이 상황 전체를 묘사하려고 노력한다. 그 노력의 일환으로 각 트럭마다 고유번호, 다리에 진입하고 나서 지난 시간, 그리고 무게를 가진 정보를 dict에 넣어서 해결하려 했으나 코드가 너무나 방대해졌따. 그래서 기각하였다.
 그 다음 시도는 간소화한 형태였다. 다리라는 스택을 만들고 다음에 들어가야할 차가 무게를 초과하면 현재 올라가있는 차가 지나가고나서 올라갈 수 있으니 현재 올라가있는 차를 보내고(스택에서 제거하고), 다리의 길이만큼 시간이 초과됐으니 answer에 해당 초만큼을 더하고 새로운 차량을 올리는 식으로. 하지만 이미 올라가있는 차량에 대한 처리가 안되므로 또 기각되었다.
 위 과정까지 진행되니 시간은 무조건 1초씩 더해야 한다는 점까지 알아냈다. 그렇게 위처럼 빈 도로를 0으로 표현하는 형태의 코드가 완성됐다.

3 Comments
  • 프로필사진 현타온코린이 2022.05.15 20:09 아주 깔끔한 코드네요. 한 수 배우고 갑니다.
    프로그래머스 정답 답안 1순위로 이게 나와야 할 것 같네요.
    코딩이 하기 싫어졌습니다 ㅠ
  • 프로필사진 Favicon of https://this-programmer.tistory.com 규도자 (gyudoza) 2022.05.15 21:17 신고 이렇게 완성돼있는 코드만 보면 뭔가 뚝딱뚝딱 수월하게 만든 것처럼 보이겠지만 전혀 아닙니다.

    수많은 코드를 쓰고 수많은 프린트문과 함께 필요없는 로직이 마구마구 섞인 상태에서 하나하나 줄이고 이런 과정을 수십번 반복한 결과값을 블로그에 남기는 거에요.
    그러니 현타오실 필요 없습니다... 저도 다른 분들이 너무나도 간결하고 깔끔한 로직으로 문제들을 푸는 거 보고 난 역시 아닌가 싶다가도 그분들도 저랑 똑같이 수십번 시도하고 수십번 실패해가면서 푸는걸 알고 괜찮아졌습니다. 화이팅입니다
  • 프로필사진 현타온코린이 2022.05.19 08:14 조언 감사합니다. 정진하겠습니다!
댓글쓰기 폼