[스택, 큐 / 프로그래머스] 42583번 : 다리를 지나는 트럭

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

 

Lv2 문제다!

 

문제 이해

- answer는 시간을 나타낸다

- bridge를 bridge_length 길이만큼의 배열로 구현해서 각 위치에 있는 트럭의 무게를 나타낸다

- weight를 비교해야하므로 해당 시간의 다리 무게를 bridge_weight를 이용한다. (이전에 sum(bridge)를 했는데, 이렇게 하면 매번 합을 구하는 연산을 해야하므로 테스트 5번에서 시간초과가 발생했다)

- 트럭이 움직이면서 시간 + 1 해주고, 가장 왼쪽에 있는 트럭 또는 0을 제거한 다음 해당 무게만큼을 다리 무게에서 제거한다

- 옮길 트럭이 남아있을 때,

• 무게 제한을 넘지 않는다면 트럭 리스트에서 트럭을 없애고, 다리에 트럭을 옮기고, 다리에 트럭의 무게를 추가해준다
• 무게 제한을 넘는다면 0을 bridge에 추가해준다

- answer를 반환한다

 

- 정답 풀이 :

 

참고한 포스트

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

 

- 시도해본 풀이 :

 

무게가 허용되는 만큼의 트럭끼리 그룹으로 묶은 다음 하나의 트럭처럼 움직이게 하고, 앞 뒤 그룹과의 겹치는 시간을 빼주는 방법으로 일반식을 만들어 봤지만, 처참하게 실패했다ㅋㅋ

 

이해한 과정은 다음과 같다

 

 

위 과정을 일반식으로 표현하면 bridge_length * (그룹 수) + 트럭 갯수 - (그룹수 - 1)이다.

하지만 결국에 틀린 답이었다는 것,,,

def solution(bridge_length, weight, truck_weights):
    n = len(truck_weights)
    #다리 건널 수 있는 트럭들끼리 나눈 그룹의 갯수
    
    result = []
    while truck_weights:
        temp = []
        while truck_weights:
            if sum(temp) + truck_weights[0] <= weight:
                x = truck_weights.pop(0)
                temp.append(x)
            else:
                break
                
        result.append(temp)
                       
    count = len(result)
    return bridge_length * count + n - (count - 1)