프로그래머스 고득점 kit(유형정리) - 다리를 지나는 트럭

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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_length  weight              truck_weights                                                       return

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

문제 자체를 이해하는데는 입력 예시 하나만 봐도 큰 어려움이 없는 문제이지만 이상한 곳에서 시간초과와 걸림돌이 많이 생겼던 문제이다.

 

※ 문제 이해

truck_weights 리스트가 대기 하는 트럭이고 하나씩 pop 시켜가면서 bridge에 넣어준다. 그렇게 들어간 bridge가 weight를 넘어서면 pop해서 다리를 건너게 되고 weight를 넘지 못할 경우 다리 길이만큼 버티면서 쌓아준다. 선입선출의 개념이므로 bridge는 Queue의 형태가 된다는 것을 문제를 읽으면서 눈치챘다면 베스트!!!

 

※ 알고리즘

문제 이해를 통해서 사실상 알고리즘 대부분을 설명했다.

 

1. 시간 저장 변수 answer를 0으로 초기화시킨다.

2. 빈 리스트 하나를 선언한다.

3. while 반복문으로 bridge가 비지 않으면 answer += 1 해주면서 truck_weights에서 대기트럭을 pop 시킨다.

4. 만약 truck_weights(대기 트럭) 리스트가 비지 않은 상태에서 bridge 리스트 안의 값과 truck_weights(대기 트럭) 리스트의 다음 진입 트럭의 무게합이 weight를 넘지 않으면 bridge에 계속 대기 트럭을 pop 시켜서 담아주고, weight를 넘으면 다리를 건너게 한다. 

 

이 알고리즘으로 문제를 풀면 바로 틀리게 된다. 빨간색으로 칠해진 부분들 때문이다.

2번의 경우 빈 리스트가 아닌 bridge_length 길이 만큼 0을 담아 놓은 리스트를 선언해주어야 한다. -> 리스트가 비게 되면 index를 인식하지 못해서 pop을 어떻게 시켜주어야 할지 모르기 때문이다. 또한, 0을 담아서 전부 0이 담아지는 경우에 4번 if문을 종료시키는 형태로 알고리즘이 흘러갈 수 있게 하기 위해서 필요하다.

 

4번의 경우 다리를 건너게 한다고 생각해서 bridge 리스트에서 pop(0)를 시켜주어야 한다고 생각했으나, 이렇게 구현할 경우 if문 조건을 아예 다르게 해야했다. 첫번째 테스트 케이스를 통과하지 못함!!! 그래서 0을 bridge에 모두 append 시켜서 모두 0이 되면 반복문을 빠져나오는 형식으로 구현을 할 수 있었다.

 

def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    Queue_bridge = []
    
    for _ in range(bridge_length):
        Queue_bridge.append(0)
        
    while Queue_bridge:
        
        answer += 1
        Queue_bridge.pop(0)
        
        if truck_weights:
            if sum(Queue_bridge) + truck_weights[0] <= weight:
                Queue_bridge.append(truck_weights.pop(0))
            else:
                Queue_bridge.pop(0)
                
    return answer

이번 문제를 통해서 몇 가지 python 문법을 알게 된 것이 있다.

 

for _ in range(bridge_length)  -> bridge_length 길이 만큼의 dummy 데이터 처리

 

Queue_bridge = []
    
    for _ in range(bridge_length):
        Queue_bridge.append(0)

이 문장의 경우 아래와 같이 표현도 가능하다.

 

1. Queue_bridge = [0] * bridge_length

 

2. Queue_bridge = [0 for _ in range(bridge_length)]

 

 

문법적인 부분과 더미 데이터를 활용해서 0으로 모두 만들어서 처리하는 리스트 방식을 기억해 둘 필요가 있는 문제였다.