프로그래머스 | 다리를 지나는 트럭 [파이썬 python]

프로그래머스

 
코드

def solution(bridge_length, weight, truck_weights):
    bridge = [0] * bridge_length    # 다리
    onbridge = sum(bridge)          # 다리 위 트럭 하중
    answer = 0                      # 시간

    # 다리 위의 트럭이 없을 때까지(=모든 트럭이 다리를 건널 때 까지)
    while bridge:
        answer += 1
        onbridge -= bridge.pop(0) # 맨 앞에 위치한 트럭이 다리를 지나면 하중 감소

        # 남은 대기 트럭이 있으면
        if truck_weights:
            # 다리 위 트럭 총 무게 + 새로운 트럭 <= 다리가 견딜 수 있는 무게이면
            if onbridge + truck_weights[0] <= weight:
                new_truck = truck_weights.pop(0)    # 대기 트럭에서 출발
                bridge.append(new_truck)            # 다리에 새로운 트럭 추가
                onbridge += new_truck               # 새로운 트럭만큼 다리 하중 증가

            # 그렇지 않으면
            else:
                bridge.append(0)                    # 다리에 0을 추가해 자리 이동 표시

    return answer

문제를 읽어보면 느끼겠지만 문제 설명이 빈약하다.
트럭이 다리를 건너는데 소요되는 시간을 구해야 하는 문제인데 시간에 대한 설명은 어디에도 없어 해당 문제의 출처를 살펴보니 트럭은 1초마다 다리를 1만큼 건넌다는 것을 알 수 있었으며, 작성한 코드를 설명하면 다음과 같다.

 
먼저, 문제 풀이를 위해 필요한 변수를 설정한다.

• bridge: 현재 다리의 상태
  • ex) [0, 7]: 길이가 2인 다리에 무게 0, 무게 7 2개의 트럭이 있다.
  • 다리 위에서 트럭의 위치 표시를 위해 0을 무게 0의 트럭이라 가정
• onbridge: 현재 다리 위에 있는 트럭 무게의 총합(=다리의 하중)
• answer: 모든 트럭이 다리를 건너는데 소요되는 시간

 

구해야 하는 것은 모든 트럭이 다리를 건너는데 소요되는 시간(answer)이므로 while문을 사용하여 bridge에 값이 존재하면(=다리 위에 트럭이 존재하면) 반복한다.

모든 과정은 1초마다 이뤄지므로 while문 시작과 동시에 answer+1을 통해 시간을 계산한다.

answer += 1 # +1초
onbridge -= bridge.pop(0) # 맨 앞에 위치한 트럭이 다리를 지나면 하중 감소

트럭이 다리를 건너는 모습은 pop() 함수를 사용해 표현하였다.

bridge는 리스트 즉, 스택이므로 다리의 맨 끝(=0번 인덱스)에 위치한 트럭은 1초가 지나면 다리를 온전히 지나 도착하게 된다.

맨 앞에 위치한 트럭을 bridge에서 pop(0)해줌과 동시에 1번 인덱스 이후의 모든 트럭들은 한 칸씩 앞으로 오게 되는 효과를 갖게 된다.

 

다리 위의 트럭들을 앞으로 한 칸씩 이동시킨 후 남은 대기 트럭이 있는지 확인한다.

# 남은 대기 트럭이 있으면
if truck_weights:
    # 다리 위 트럭 총 무게 + 새로운 트럭 <= 다리가 견딜 수 있는 무게이면
    if onbridge + truck_weights[0] <= weight:
        new_truck = truck_weights.pop(0)    # 대기 트럭에서 출발
        bridge.append(new_truck)            # 다리에 새로운 트럭 추가
        onbridge += new_truck               # 새로운 트럭만큼 다리 하중 증가

    # 그렇지 않으면
    else:
        bridge.append(0)                    # 다리에 0을 추가해 자리 이동 표시

대기 트럭이 존재하면 대기 트럭 중 0번째 트럭이 다리에 진입할 수 있는지 확인한다.

다리 위 트럭 총 무게 + 새로운 트럭 <= 다리가 견딜 수 있는 무게이면 대기 트럭에서 pop을 통해 new_truck으로 정의하고 new_truck을 다리(bridge)와 다리 하중(onbridge)에 반영해 준다.

그렇지 않으면 다리 위의 트럭들이 이동한 것을 표시하기 위해 다리(bridge)에 0을 추가한다.

0을 추가하는 이유는 다리의 길이(bridge_length)에 맞게 각 트럭들의 위치를 표시해야 하기 때문이다.

 

대기 트럭이 더 이상 존재하지 않으면 다리 위의 트럭들만 모두 건널 수 있도록 1초마다 pop을 한 번씩 해준다.

모든 트럭이 다리를 건넜으면 while문을 탈출해 answer를 리턴한다.

 

 

처음에는 while문의 조건을 sum을 사용해 weight와 비교하는 방법으로 코드를 작성했는데 시간초과가 발생하는 테스트 케이스가 있었다.

시간 초과의 원인이 sum이라는 힌트를 얻고 다리 위의 트럭들의 총무게를 나타날 새로운 변수를 설정해 주니 바로 해결되었다.

이 부분만 잘 해결했다면 나머지는 스택 개념으로 충분히 풀 수 있는 문제이다.