[프로그래머스/Python] 스택/큐 Level 2. 다리를 지나는 트럭

스택/큐(Stack/Queue)

출체빈도 보통 | 평균 점수 높음

LIFO, FIFO, push & pop! 스택과 큐를 이용해서 문제를 풀어보세요.

 

---

문제 2. 다리를 지나는 트럭

 

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

제한사항

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

 

 

---

좀 오래 전에 풀어두고 다시 코드 리뷰를 하려니까 기억이 안난다.

앞으로는 밀리지 않아야겠다.~

내 기억엔 내가 풀다가 안풀려서 다른 분들 코드를 참고했던 것 같다.

 

 

- 처음에 작성한 코드

 

def solution(bridge_length, weight, truck_weights):
  if len(truck_weights)==1 : return bridge_length+1
  bridge = [0]*len(truck_weights)
  first = 0 
  last = 0 
  out = -1 
  time = 1
  bridge[0] += 1 

  while out < len(truck_weights) :
    if sum(truck_weights[first:last+1]) + truck_weights[last+1] <= weight: last += 1
    for i in range(first, last+1) : 
      bridge[i]+=1 # 2
      if bridge[i] == (bridge_length + 1) :
        out = i # 0
        bridge[out] = -1
        first = out + 1 # 1
      if i==first : time += 1
    if(last==len(truck_weights)-1) :
      while(bridge[last]<bridge_length+1) :
        bridge[last] += 1
        time += 1
      break
  
  return time

 

딱 봐도 코드가 더러움.

 

채점 결과

정확성: 23.1

합계: 23.1 / 100.0

 

당시에 나는 다리 위에 있는 트럭 중에 가장 앞에 있는 트럭의 인덱스를 first, 끝의 인덱스를 last로 했던 것 같다.

만약에 끝의 인덱스가 트럭 배열의 마지막 인덱스라면 나갈 때 까지 time ++ 해주었다.

 

 

 

- 그리고 수정한 코드

 

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

    return time

 

채점 결과

정확성: 92.3 -> case 5 : 시간초과

합계: 92.3 / 100.0 

 

-> 위의 코드랑 비교하면 장족의 발전

 

 

- 나의 로직

 

while 문을 돌면서 다리 가장 앞에 있는 것을 뺀다. 트럭일 수도 있고, 아무것도 없을 수도 있고.

아직 truck_weights에 트럭이 남아 있다면 다리 위에 있는 트럭들의 무게의 합과 들어오는 트럭의 무게의 합을 비교한다.

들어올 수 있으면 다리에 트럭을 append하고 weights 배열에서 꺼낸다.

이런 식으로 반복하다보면 truck_weights에는 트럭이 없을 것이다.

 

근데 이렇게 하면... 시간 초과가 발생한다.

예상하기에는 pop(0)에서 시간복잡도가 커진 것이 아닐까라는 생각이 들었다.

어떻게 해결해야 할지 몰라서 다른 분들의 코드를 읽었다.

 

 

 

 

- 다른 분의 코드

def solution(bridge_length, weight, truck_weights):
    time = 0
    on_bridge = []
    on_time = []
    
    while(truck_weights or on_bridge) :
        time += 1
        if(on_time) :
            if(on_time[0] + bridge_length == time) :
                on_bridge.pop(0)
                on_time.pop(0)
        if(truck_weights) :
            if(sum(on_bridge) + truck_weights[0] <= weight) :
                on_bridge.append(truck_weights.pop(0))
                on_time.append(time)
    
    return time

 

on_time은 트럭이 들어간 시간을 담는 배열

on_bridge는 다리 위에 있는 트럭의 무게를 담는 배열

if(on_time[0] + bridge_length == time) : -> 트럭이 나가야 함

이 코드에도 pop(0)가 있는데 시간초과가 왜 안뜨는지는 모르겠다. ㅠㅠ