[Stack/Queue] 다리를 지나는 트럭 JAVA 솔루션

문제

다리를 건너는 트럭

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다.

트럭은 1초에 1만큼 움직이며, 다리 길이는 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 이하입니다.

풀이

사실 여러 문제 풀이들을 구글링 해서, 최대한 효율적인 풀이로 리팩토링 했다.

핵심 아이디어는

1. 바깥 반복문을 통해 초 i를 1씩 계속 증가시켜 준다.
2. return 로직인 나가는 로직을 먼저 짠다.
3. (idx-timeQueue.size())를 통해서 weight의 순서를 계산할 수 있다. 따라서 다른 큐가 불필요하다.
4. LinkedList Queue의 O(1) 매써드 만을 사용하므로, 거의 선형 시간에 끝나는 알고리즘이라 할 수 있다. (for반복문 내 모든 매써드 O(1))

 

xxxxxxxxxx
import java.util.LinkedList;
import java.util.Queue;
​
​
public class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int idx = 0;
        int bridge_weight = 0;
        Queue<Integer> times = new LinkedList<>();
        for (int i = 1; ; i++) { //초는 1부터 시작.
            //트럭 나가는 로직
            if ((times.size() > 0) == true) { //시간이 큐에 존재하고
                if (i - times.peek() == bridge_length) { //맨 앞에서 달리는 트럭이 다리를 다 건넜으면...
                    bridge_weight -= truck_weights[idx - times.size()];//현재 총 무게에서 무게 빼줌
                    int finish_time = bridge_length + times.poll();
                    if (idx >= truck_weights.length && times.size() == 0) {
                        return finish_time;
                    }
​
                }
            }
            //트럭 진입 로직
            if (idx >= truck_weights.length || bridge_weight + truck_weights[idx] > weight)
                continue;
            else {
                bridge_weight += truck_weights[idx];
                times.add(i);
                idx++;
                continue;
                    /*idx는 가장 마지막에 들어간 트럭 의미.
                    idx가 증가하고, queue의 크기가 감소하므로, idx-queue.size는 0부터 점차 증가하겠죠? ^^
                    따라서 처음에 들어간 트럭의 무게인 인덱스 0부터 하나씩 계산이 가능합니다.*/
            }
        }
    }
}
​