다리를 지나는 트럭 문제에 대한 설명은 다음의 링크를 참고해주시기 바랍니다. 문제 설명
우선, 다리를 지나는 트럭은 truck_weights로 주어진 트럭의 순서가 변경될 수 없습니다. 따라서 정해진 순서를 기반으로 모든 트럭이 다리를 건너는 최소 시간을 정답으로 구합니다.
예시는 자세한 설명을 동반하고 있어 질문하기 목록에 있는 예시 테스트 케이스 중 하나로 문제 해결 순서를 확인해보겠습니다. 질문하기
bridge_length = 5, weight = 5, truck_weights = [2, 2, 2, 2, 1, 1, 1, 1, 1]
1 초 2 무게의 트럭이 들어왔다. 현재 다리의 무게 = 2
2 초 2 무게의 트럭이 들어왔다. 현재 다리의 무게 = 4
6 초 2 무게의 트럭이 나갔다. 현재 다리의 무게 = 2
6 초 2 무게의 트럭이 들어왔다. 현재 다리의 무게 = 4
7 초 2 무게의 트럭이 나갔다. 현재 다리의 무게 = 2
7 초 2 무게의 트럭이 들어왔다. 현재 다리의 무게 = 4
8 초 1 무게의 트럭이 들어왔다. 현재 다리의 무게 = 5
11 초 2 무게의 트럭이 나갔다. 현재 다리의 무게 = 3
11 초 1 무게의 트럭이 들어왔다. 현재 다리의 무게 = 4
12 초 1 무게의 트럭이 들어왔다. 현재 다리의 무게 = 5
13 초 2 무게의 트럭이 나갔다. 현재 다리의 무게 = 3
13 초 1 무게의 트럭이 들어왔다. 현재 다리의 무게 = 4
14 초 1 무게의 트럭이 들어왔다. 현재 다리의 무게 = 5
남은 트럭 = [1,1,1,1,1]
정답: 19초
위의 과정을 통해서 최소 시간이 결정되게 됩니다. 다음은 문제를 해결함에 있어 유의해야 할 사항입니다.
- 오직 트럭이 나간 후에 여유 무게가 있다면 같은 시간에 트럭이 들어올 수 있다.
- 모든 트럭이 다리에 올라간 상태라면 현재 시간에 bridge_length를 더해주면 최소 시간이 된다.
첫 번째는 같은 시간에 처리될 수 있는 경우는 트럭이 나갔을 때 들어오는 경우뿐이라는 것입니다. 여유 공간이 있어 트럭이 들어온 후에 나가는 경우는 현재 시간에 +1을 한 후에 처리해야 합니다. (테스트 케이스 4,5,6,9번을 틀렸다면 이 부분을 주의 깊게 봐야 한다)
두 번째는 모든 트럭이 다리에 올라갔다면 얼마가 남았든 상관없이 현재 시간에 bridge_length를 더해주면 됩니다. 왜냐하면 현재 시간은 마지막 트럭이 다리에 올라간 시간이므로 마지막 트럭이 다리를 빠져나갔다면 다른 트럭들도 빠져나갔을 것이기 때문입니다.
두 가지 유의사항에 만족하며 코드를 작성하면 다음과 같습니다.
def solution(bridge_length, weight, truck_weights):
queue = []
answer, current_weight = 0, 0
while truck_weights:
if current_weight + truck_weights[0] <= weight:
truck = truck_weights.pop(0)
current_weight += truck
queue.append((answer, truck))
answer += 1
else:
time, truck = queue.pop(0)
current_weight -= truck
answer = max(answer, time + bridge_length)
return answer if not queue else answer + bridge_length
모든 트럭이 다리에 올라가기 전까지 반복문을 돌면서 여유 무게가 있다면 트럭을 다리에 올리고 아니라면 가장 오랫동안 머무른 트럭을 지나가게 만들어주는 과정을 반복합니다.
해당 문제는 큐를 중심으로 문제를 해결할 수 있습니다. 트럭을 처리하는 순서, answer를 초기화해주는 시점 등 여러 조건들이 처리되므로 문제의 논리를 어떤 순서로 처리해줄 것인지 생각하는 것이 더 중요한 문제였습니다.
'📦 아카이브' 카테고리의 다른 글
버블 정렬은 뭐야? (0) | 2022.07.29 |
---|---|
프로그래머스 76502 괄호 회전하기 (0) | 2022.07.28 |
프로그래머스 42747 H-Index (0) | 2022.07.20 |
프로그래머스86971 전력망 둘로 나누기 (0) | 2022.07.19 |
연결리스트는 뭐야? (0) | 2022.07.08 |
댓글