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

문제 링크

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

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

풀이 - 다른 블로그 참고 

- 왤케 어렵지................. 문제 이해가 안됐다

- brigde_length를 1만큼 지날 때마다 1초가 지난다고 한다.

- q 는 다리 길이만큼 다리를 만들어주었다. 

- q에서 하나의 차가 다리를 건너고, 이미 있는 차와 다음에 올 차의 무게 합이 한계 무게를 넘지 않으면 다음 차도 다리에 올린다. 

- 무게의 합이 한계를 넘으면 0을 추가하여 이미 있는 차를 앞으로 옮긴다. 

# 테스트 케이스 5번만 시간초과 
def solution(bridge_length, weight, truck_weights):
  # 다리 
  # q = [0 for _ in range(bridge_length)로  선언하면 시간초과 발생하지 않음 
  q = [0] * bridge_length
  answer = 0 

  while q:
    # 시간 +1 
    answer += 1 
    
    # 다리 건넘 
    q.pop(0)

    if truck_weights:
      # 한계 무게를 넘지 않으면 
      if truck_weights[0] + sum(q) <= weight:
        # 다음 차도 다리에 올림 
        q.append(truck_weights.pop(0))
      else:
        q.append(0)
    
  return answer

+ 2022.03.28 다시 풀어봄 

- deque 사용해서 풀이

- q = deque([0] * bridge_length) 로 다리를 만들어줌

- while 문 반복

1. 시간 + 1, 다리 맨 앞 보냄 

2. 다리에 올라온 트럭들의 무게 합 + 다음에 올 트럭의 무게가 한계 무게보다 작거나 같으면 큐에 트럭 추가

3. 무게를 초과하면 큐에 0 추가 

- 시간 초과가 발생하였다. 찾아보니 다리에 올라온 트럭들의 무게의 합(큐의 합)을 구할 때 sum 을 사용해서 그렇다고 한다. 

#시간 초과 

from collections import deque 
def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    # 트럭 
    q = deque([0] * bridge_length)
    # 다음에 올 트럭의 위치를 가리키는 인덱스 
    index = 0 
    
    while q :
    	# 시간 1초 증가 
        answer += 1
        # 다리에 맨 앞 하나 보냄 
        q.popleft()

		# 건널 트럭이 남아있으면 
        if index < len(truck_weights):
        	# 한계 무게보다 작으면 
            if sum(q) + truck_weights[index] <= weight :
                q.append(truck_weights[index])
                index += 1
            else:
                q.append(0)        
        
    return answer

- 따라서 s에 다리에 올라온 트럭들의 무게를 저장해주었다. 

from collections import deque 
def solution(bridge_length, weight, truck_weights):
    answer = 0
    # 다리에 올라온 트럭들의 무게 합 
    s = 0 
    # 트럭 
    q = deque([0] * bridge_length)
    # 다음에 건널 트럭의 위치를 가리키는 인덱스 
    index = 0 
    
    while q :
    	# 시간지남 
        answer += 1
        # 다리에 올라온 트럭들의 무게 합 갱신 
        x = q.popleft()
        s -= x 
        
        if index < len(truck_weights):
            if s + truck_weights[index] <= weight :
            	# 다리에 올라온 트럭들의 무게 합 갱신 
                s += truck_weights[index]
                q.append(truck_weights[index])
                index += 1
            else:
                q.append(0)        
        
    return answer