42583 다리를 지나는 트럭

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

 

# trial 1 -> 실패

- onbg를 계속 누적으로 더한 것이 문제. 앞부터 쭉 묶어서 한 패키지를 구성하는게 아님.

- 그리고 prev, next가 같은 다리에 있다고 해서 무조건 1차이 나는 것이 아니라, 멀리 떨어져있을 수가 있음.

- 반례:

bridge_length = 10

weight = 100

truck_weights = [50, 30, 20, 10, 10, 10, 10, 10, 10]

from collections import deque

def solution(bridge_length, weight, truck_weights):
    
    trucks = deque(truck_weights)
    t = 1 + bridge_length
    onbg = trucks.popleft()
    
    while trucks:
        new = trucks.popleft()
        
        if onbg + new <= weight:
            onbg += new
            t += 1
        else:
            onbg = new
            t += bridge_length
            
    return t

 

 

# trial 2 -> 성공

- 여러 코드들을 참조해서 풀었음.

- 시간 간격을 체크하기 위해 [0] * bridge_length로 초기화한 아이디어

- 배열의 각 위치는 1초 단위의 거리를 나타냄

- 문제 조건) onbg에서 아예 나가는 것이 건넒을 완료한 것으로 간주됨

from collections import deque

def solution(bridge_length, weight, truck_weights):
    
    trucks = deque(truck_weights)
    onbg = deque([0] * bridge_length)  
    t = 0
    cur_weight = 0
    
    while onbg:
        t += 1
        
        done = onbg.popleft()
        cur_weight -= done
        
        if trucks:
            if cur_weight + trucks[0] <= weight:
                new = trucks.popleft()
                onbg.append(new)
                cur_weight += new
            else:
                onbg.append(0)
                
    return t

 

 

[개선할 점]

- 시간 초와 상태에 대한 직관이 더 필요하다.