알고리즘 풀이 - 프로그래머스(다리를 지나는 트럭, 큐)

 

문제 설명

 

복수의 트럭이 강을 가로지르는 1차선 다리를 순서대로 건넌다. 모든 트럭이 다리를 건너는데 걸리는 시간을 알아내야 한다. 트럭은 1초에 1만큼 이동한다.

배열 bridge_length : 다리의 길이
배열 weight : 다리가 견딜 수 있는 무게
배열 truck_weights : 건너고자 하는 트럭들의 무게

단, 트럭이 다리에 완전히 오르지 않고 일부만 오른 경우 등은 고려하지 않는다.

 

예시

 - 다리 길이가 2, 견딜 수 있는 무게 10Kg에 무게가 [7, 4, 5, 6]인 트럭이 순서대로 최단 시간에 다리를 건너는 방법은 아래와 같다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 중인 트럭
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초의 시간이 걸린다.

 

제한조건

 - bridge_length는 1 이상 10,000이하
 - weight는 1 이상 10,000 이하
 - truck_weights의 길이는 1 이상 10,000이하
 - 모든 트럭 무게는 1 이상 weight 이하

 

해결 방법 1 - Queue를 이용해 해결

 

Queue를 선언해 현재 다리를 지나고 있는 트럭의 무게를 저장할 수 있다. Queue에서 빠져나오기 전까지 트럭은 다리를 지난 상태가 아닌 것으로 간주한다. 현재 Queue에 저장된 트럭의 무게가 견딜 수 있는 무게를 넘어서려 한다면 Dummy를 집어넣어(0의 무게) 메꾼다. Queue의 크기는 bridge 의 길이를 최대값으로 갖는다. Dummy 또는 트럭으로 꽉 차서 지날 수 없다면 가장 먼저 들어간 트럭 또는 Dummy를 제외하여 무게를 비교하고 다음 트럭이 건널 지 결정하는 방식으로 진행한다.다음의 코드를 보자

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Queue<Integer> queue = new LinkedList<>();
        int current_weight = 0;
        int passed = 0;
        for(int i=0; i < truck_weights.length; i++){
            int next_truck = truck_weights[i];
            if(current_weight + next_truck > weight){
                while(queue.size() < bridge_length){
                    queue.offer(0);
                    answer++;
                }
            }
            while(true){
                int p = 0;
                if(queue.size() == bridge_length || current_weight+next_truck > weight){
                    p = queue.poll();
                    current_weight -= p;
                    if(p > 0){
                        passed++;
                    }
                }
                if(current_weight+next_truck <= weight){
                    break;
                }
                queue.offer(0);
                answer++;
            }
            queue.offer(next_truck);
            current_weight += next_truck;
            answer++;
        }
        if(queue.size() != bridge_length){
            answer += (bridge_length-queue.size());
        }

        while(passed != truck_weights.length){
            int poll = queue.poll();
            if(poll > 0){
                passed++;
            }
            answer++;
        }
        return answer;
    }
}

 

해결 방법2 - Queue를 이용해 해결(더 짧은 코드)

 

Queue를 사용하는 것은 동일하나 Dummy를 사용해 Queue의 크기를 Bridge의 길이와 맞추지 않고 Truck Class를 별도로 정의하여 다리에 진입한 시간과 무게를 저장한다. 또한 Truck의 순서를 기준으로 반복문을 진행하지 않고 시간을 지속적으로 보내가며 반복문을 수행한다.

시간이 지나가며 다리에 진입한 시간과 현재 시간의 차이가 전체 다리 길이와 같아지는 경우 Queue에서 빼내고  현재 다리의 지탱 무게를 조정한다. 이 과정을 거치기 때문에 Bridge에 현재 빈 공간이 여유가 없는지를 체크할 코드를 반영하지 않아도 된다.

이후, 다음 대기 중인 트럭의 무게와 현재 무게를 더해 트럭이 진입 가능한 지 체크한 뒤 Queue에 넣는다. 현재 다리에 진입한 트럭의 숫자가 전체 트럭의 숫자와 일치하면 반복문을 빠져나온다.마지막으로, 제일 끝으로 다리에 진입한 트럭은 다리의 시작점 부분에 위치하므로 다리의 길이만큼 더해주고 해당 값을 반환한다. 아래의 코드를 보자.

package com.test;

import java.util.LinkedList;
import java.util.Queue;

public class Test {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Truck> queue = new LinkedList<>();
        int currentWeight = 0;
        int enteredTruck = 0;
        int answer = 0;
        while(enteredTruck < truck_weights.length){
            answer++;
            if(!queue.isEmpty()){
                if(answer - queue.peek().startTime == bridge_length){
                    int p = queue.poll().weight;
                    currentWeight -= p;
                }
            }
            int waitingFront = truck_weights[enteredTruck];
            if(currentWeight + waitingFront <= weight){
                queue.offer(new Truck(answer, waitingFront));
                enteredTruck++;
                currentWeight += waitingFront;
            }
        }
        answer += bridge_length;
        return answer;
    }
    private static class Truck{
        int startTime;
        int weight;
        public Truck(int startTime, int weight){
            this.startTime = startTime;
            this.weight = weight;
        }
    }
}

 

위 코드의 테스트 결과는 아래와 같다.