[프로그래머스] 다리를 지나는 트럭 level2 - python

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

 

 

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

 

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

 

 

따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.

 

 

 

 

 

 

 

 

입출력 예

 

 

 

---

이 문제는 총 고려해야 하는 것이 2가지가 있다. 다리 길이와 다리가 버틸 수 있는 무게 인데, 다리의 길이를 직관적으로 표현하기 위해 다리의 길이 만큼 0으로 채운 리스트를 생성해주었다. 그 후에 truck_weights 의 숫자 하나씩 append하여 다리를 건너는 트럭을 구현하였다.

 

다음은 위 문제를 구현할 방식을 그림으로 표현한 것이다.

 

 

처음에 bridge_length 만큼 0의 개수를 가진 리스트를 생성하고, count 변수를 0으로 초기화한다. 그 후에 트럭의 무게가 차례대로 append되며 동시에 count 역시 1씩 증가한다. 이를 통해 모든 트럭이 다리를 통과했을 때 소요되는 시간을 구현하였다. 

 

 

 

 

 

 

 

 

Stack 사용

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

다음은 위의 방식을 토대로 구현한 알고리즘인데 시간 초과가 나는 문제가 생겼다. 

 

이를 해결하기 위해서는 연산량을 줄여야하기 때문에 코드를 하나씩 보며 연산량이 불필요하게 많아지는 지점을 찾아보았다. 

 

리스트에 append, pop 하는 과정은 큰 연산이 일어나지 않으며, count에 1씩 더하는 것은 당연히 문제되지 않는다. 다음으로 while문을 의심해볼 수 있었지만 따로 문제될 건 없었다.

 

그리고 불필요한 연산량이 발생되는 지점을 찾았는데 바로 sum 이다. bridge는 0으로 채워져 있는 리스트였으며, 트럭의 무게가 append된다 해도 리스트에 0은 많이 남아있다. 하지만 sum(bridge)를 하면서 굳이 더하지 않아도 되는 0을 계속 더해주게 되었고 이는 시간복잡도 O(N) 이 계속 더해지게 되었다. 이를 해결하기 위해 bridge_weight 라는 변수 하나를 더 생성하여 0을 계속 더하는 불필요한 연산을 제거해주었다.

 

def solution(bridge_length, weight, truck_weights):
    bridge = [0] * bridge_length
    count = 0
    bridge_weight = 0
    
    while bridge:
        if bridge[0] != 0:
            bridge_weight -= bridge[0]
        
        bridge.pop(0)
        count += 1
        
        if truck_weights:
            if bridge_weight + truck_weights[0] <= weight:
                truck = truck_weights.pop(0)
                bridge.append(truck)
                bridge_weight += truck
                
            else:
                bridge.append(0)
    
    return count

 

이와 같이 코드를 변형해주니 시간 초과 문제없이 잘 돌아갔다.