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

프로그래머스 코딩테스트 문제입니다.

https://programmers.co.kr/learn/challenges?tab=weekly_challenges

코딩테스트 연습

 

문제

https://programmers.co.kr/learn/courses/30/lessons/42583?language=python3 

코딩테스트 연습 - 다리를 지나는 트럭

 

내가 작성한 코드

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = deque([0] * bridge_length)
    truck_weights = deque(truck_weights)
    bridge_weight = 0

    while bridge:
        bridge_weight -= bridge.popleft()
        if truck_weights:
            if bridge_weight + truck_weights[0] <= weight:
                bridge.append(truck_weights.popleft())
                bridge_weight += bridge[-1]
            else:
                bridge.append(0)
        answer += 1

    return answer

• 큐
  
  • 다리의 length만큼 0을 추가 (bridge)
  • 매 loop마다 bridge에서 하나씩 dequeue, 1초 추가
  • 다리 무게가 되면 truck 추가, 아니면 0 추가

 

다른 사람이 작성한 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    bridgeWeight = 0 # 다리 위의 트럭 무게
    waiting = deque(truck_weights) # 대기 트럭 큐
    bridge = deque([0 for _ in range(bridge_length)]) # 다리 길이만큼 0으로 채운다.
    
    while len(waiting) or bridgeWeight > 0: # 대기 트럭이 있거나 이동 중인 트럭이 있는 동안 반복
        removedTruck = bridge.popleft() # 다리에서 하나 제거
        bridgeWeight -= removedTruck
        
        if len(waiting) and bridgeWeight + waiting[0] <= weight: # 새 트럭이 다리에 올라갈 수 있으면
            newTruck = waiting.popleft()
            bridgeWeight += newTruck
            
            bridge.append(newTruck) # 대기 트럭에서 하나 빼서 다리에 올림
            
        else: # 새 트럭이 다리에 올라갈 수 없으면
            bridge.append(0) # 오른쪽에 0을 삽입해서 다리 길이 유지
            
        time += 1
    return time

• 아래 블로그에서 본 위 코드를 참고하여 풀었음
  
  • 참고했지만 코드는 똑같다...

https://latte-is-horse.tistory.com/130

[프로그래머스 lv2] 다리를 지나는 트럭 (파이썬)

기억해야할 것

• 효율성
  
  • 이 문제가 너무 어려워서 결국 찾아봤음
  • 1초마다 loop를 돌면 최악의 경우 10_000 * 10_000 이므로 시간초과
  • 불필요한 과정을 skip하는 방법을 생각해봄
    • 다리에 트럭 하나만 있으면 bridge_length만큼 skip
  • 과정이 복잡하고 어려워짐
    • 트럭을 하나씩 다리에 추가할 때, bridge_length 이상 들어온다면?
    • 추가된 트럭에 대한 시간 경과 계산 (bridge_length - 다리 위 트럭 수 + 1 후 첫 트럭 나감)
    • 다리 위 트럭이 3대였는데, 2대 빠지고 1대 들어오는 복잡한 경우
• 그래도 풀기
  • 효율성을 생각하지 말고 문제를 먼저 풀어야함
  • 다 푼 후 효율성을 고려하여 다시 수정하기