https://programmers.co.kr/learn/courses/30/lessons/42583
문제
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.
solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
제한사항
- bridge_length는 1 이상 10,000 이하입니다.
- weight는 1 이상 10,000 이하입니다.
- truck_weights의 길이는 1 이상 10,000 이하입니다.
- 모든 트럭의 무게는 1 이상 weight 이하입니다.
입출력 예
풀이
문제에 트럭이 다리를 건너는 시간에 대한 언급이 없는데 예시를 보면 트럭은 1초에 1만큼 지날 수 있는 것으로 추정된다.!.!
트럭이 순서대로 건너야 하므로 선입선출, 즉 queue를 사용해서(but 리스트를 사용한 큐 ,,) 문제를 풀 수 있다.
먼저 bridge_length의 길이를 가진 리스트로 bridge를 만든다. bridge_length가 2라면 [0, 0] <- 요론 느낌으로 !
그 다음엔 bridge가 빌 때까지 아래 내용을 반복해주면 된다.
1. answer(시간) += 1, bridge에 새로운 트럭을 넣기 위해 기존의 원소 중 첫번째 원소를 pop한다.
2. 만약 truck_weights가 빈 리스트가 아니라면 대기 트럭이 남아있다는 뜻이므로 다음의 올 트럭이 다리 위로 올라갈 수 있는지를 판단해야 한다. 현재 다리 위 트럭의 무게와 다음의 올 트럭의 무게를 더했을 때 다리가 견딜 수 있으면 truck_weights에서 빼서 bridge에 올려주고, 견딜 수 없으면 bridge 길이 유지용으로 0만 추가하고 지나간다.
bridge가 빈 리스트가 되면 반복이 끝나고, 모든 트럭이 다리를 지나는데 걸린 시간인 answer을 리턴한다.
코드
def solution(bridge_length, weight, truck_weights):
answer = 0
bridge = [0 for _ in range(bridge_length)]
while bridge:
answer += 1
bridge.pop(0)
if truck_weights:
# 현재 다리 위 트럭 무게 + 다음에 올 트럭 무게 <= weight 라면, truck_weights에서 pop & bridge에 append
if sum(bridge) + truck_weights[0] <= weight:
truck = truck_weights.pop(0)
bridge.append(truck)
# 그렇지 않다면 pass (bridge의 길이 유지를 위해 0 append)
else:
bridge.append(0)
return answer