[알고리즘] 프로그래머스 - 다리를 지나는 트럭 - JAVA

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

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

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.

입출력 예

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

---

문제 이해

다리의 길이만큼 트럭이 여러개 올라 갈 수 있다. 이 때 트럭의 대수가 다리의 길이와 작거나 같아도 weight를 초과하면 트럭은 올라 갈 수 없다.

 

truck_weights 배열 순서대로 트럭이 지나가야 할 때, 모든 트럭이 다리를 빠져나가는 최단시간을 구하는 문제이다.

풀이과정

두 개의 큐를 사용하여 문제를 해결하였다. 

 

첫 번째 큐는 다리를 지나야 할 트럭들을 넣은 큐이며 두 번째 큐는 다리를 지나고 있는 트럭들을 넣은 큐이다.

 

아래의 사항들을 고려하여야 한다.

 

1. 트럭 큐에 모든 트럭 엔트리들을 집어넣는다.

 

2. 다리 길이보다 다리에 올라가 있는 트럭의 수가 적으면 다리 큐에 트럭을 넣은 후 트럭의 합계 무게를 올려준다. (이 때, 트럭을 넣음으로써 최대 무게를 초과하지 않는지 확인해야한다.)

 

3. 두 번째 큐(다리에 올라가있는)의 peek가 다리를 모두 지나갔을 경우(time이 다리 길이만큼일 때)  큐에서 빼준 후 합계 무게에서 큐에서 빠진 자동차의 무게를 뺀다.

 

4. 반복문이 한 싸이클 돌아갈때마다 answer값과 다리 큐에 있는 트럭들의 time 값을 증가시켜준다.

 

소스코드

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 1;
        
        int totalWeight = truck_weights[0];
        Queue<Truck> bridge = new LinkedList<>();
        Queue<Truck> wait = new LinkedList<>();
        
        for (int i : truck_weights) {
            wait.offer(new Truck(i, 0));
        }
        
        bridge.offer(wait.poll());
        
        while (!wait.isEmpty()) {
            
            for (Truck truck : bridge) {
                truck.time++;
            }
            
            if (bridge.peek().time == bridge_length) {
                Truck truck = bridge.poll();
                totalWeight -= truck.weight;
            }
            
            if (bridge.size() <= bridge_length) {
                int nextWeight = totalWeight + wait.peek().weight;
                
                if (nextWeight <= weight) {
                    bridge.add(wait.poll());
                    totalWeight = nextWeight;
                }
            }
            answer++;
        }
        
        return answer + bridge_length;
    }
    
    private class Truck {
        int weight, time;
        
        public Truck(int weight, int time) {
            this.weight = weight;
            this.time = time;
        }
            
    }
}