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

 

 

 

안녕하세요~

27년차 진로탐색꾼 조녁입니다!

 

1일 1코테가 진작에 막을 내리고 ... 정확히 3주만에 포스팅입니다!

 

그 사이에 제가 무엇을 했냐면!! 백준에서 베이직한 코테들을 다 풀어봤고, 자료구조랑 알고리즘 공부를 했습니다! (스마게도 다녀옴)

계속 문제를 풀면서 벽을 많이 느껴서 기초를 다지고 다시 풀어야겠다고 느꼈습니다! (며칠 전에 삼성 코테도 다녀왔어요 ㅎ..)

 

그래서 이제 구조별로 고득점Kit을 풀건데 시작은 역시나 스택/큐입니다! 

개인적인 문제 풀이 외에도 다른 분들 코드도 최소 2개는 쳐보려고합니다!! 목표는 구조를 익히는 것이니까요.

 

· 문제명 : 다리를 지나는 트럭

· 사용 언어 : Python3

· 난이도 : Level2

· 문제 설명 

programmers.co.kr/learn/courses/30/lessons/42583

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

 

다양한 방법이 있었는데 풀려도 속도가 안나는 케이스들이 있습니다.

 

풀이1 

 

- 엄청 느리다. 구조를 다듬어야 할 것 같다.

 

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

    while True :
        if len(truck_weights) == 0 and sum(bridge) == 0:
            break

        answer += 1
        bridge.pop(0)
        nextNum = 0

        if truck_weights: 
            if sum(bridge) + truck_weights[0] <= weight:
                nextNum = truck_weights[0]
                truck_weights.pop(0)
        bridge.append(nextNum)

    return answer

 

 

풀이2

 

-큐를 안쓰고 풀었다. 마찬가지로 느리지만 코드가 간결했다.

 

def solution(bridge_length, weight, truck_weights):
    bridge = [0]*bridge_length #다리 생성 [0,0, ...0,0]
    cnt  = 0 #걸린 시간

    #다리 위가 빌때까지 반복
    while bridge:
      cnt += 1
      bridge.pop(0)
      #들어갈 트럭이 있을 때, 안에 트럭과 들어갈 트럭의 무게 고려
      if truck_weights:
        if sum(bridge) + truck_weights[0] <= weight: #들어갈만하면
            bridge.append(truck_weights[0])
            truck_weights.pop(0)
        else:
             bridge.append(0)
    return cnt

 

 

풀이3

 

-큐를 사용했고, while문의 조건을 트럭들이 다리에 다 오를 때까지로 잡고 마지막 트럭이 건너는 시간은 While문이 끝나고 다리의 길이만큼 더해줬다. 이게 시간 단축이 많이 됐다.

 

from collections import deque

def solution(bridge_length, weight, truck_weights):
  bridge = deque([0]*bridge_length)
  total_weight = 0
  sec = 0
  truck_weights.reverse() 

  while truck_weights:
    total_weight -= bridge.popleft()
    sec +=1
    if total_weight + truck_weights[-1] > weight:
      bridge.append(0)
    else:
      truck = truck_weights.pop()
      bridge.append(truck)
      total_weight += truck
  
  sec +=bridge_length

  return sec
    

 

https://link.coupang.com/a/rGILU

[한빛미디어]이것이 취업을 위한 코딩 테스트다 with 파이썬

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."