프로그래머스 - 다리를 지나는 트럭(Java, 자바)

문제 링크

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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

 

---

문제 풀이 과정

이 문제를 보자마자 제일 먼저 떠오른건 큐를 이용해서 풀이를 해야한다는 것이다.
큐는 선입선출의 특징을 가지고 있으며, 트럭은 배열의 순서에 따라서 움직이기 때문에 큐 자료구조를 이용해서 문제를 해결하면 된다.

또 여기서 한가지 더 알수 있는 정보가 있다. 다리에 올라 갈 수 있는 트럭의 수는 다리의 길이 만큼 가능하다고 한다. 결국 다리의 길이는 큐의 크기가 된다.

여기서 발생할 수 있는 경우의 수는 큐가 비여있을 때, 가득차있지 않을때, 가득차있을 때 3가지의 경우의 수가 나온다.

큐가 비여있다는 것은 다리위에 아무것도 없다는 뜻이 된다. 이때는 트럭을 다리위에 올린 다음 다리에 올라간 트럭의 무게를 더하는 변수 sum에 해당 값을 누적하고 시간도 추가하여 올려준다.

이제 가득 차있지 않을 때를 보자.
현재 다리위에 7kg 트럭 한대가 올라가 있고, 다음 트럭의 무게를 현재 무게와 더해서 추가로 올라갈 수 있는지 본다.
무게가 초과되어 더이상 트럭을 추가하여 올릴 수 없다. 이럴 경우 0kg 짜리 트럭을 올려주고 시간도 추가한다.

이제 큐가 가득 찬 상황이다.
이때는 앞에 있는 트럭을 poll()해주면 된다. poll() 할때는 별도로 시간이 추가 되지 않는다.

 

여기서 누적 무게를 가지고 있는 sum 에서 poll() 한 값을 빼주어야 한다.

이번 경우는 가득 차지 않고 추가로 트럭을 올릴 수 있는 경우다.
이때 큐에 트럭의 무게를 넣어 주고, 시간도 추가한다.

 

이것을 트럭 배열 끝날 때까지 반복하면 된다.

 

마지막 트럭까지 반복문이 진행되면 마지막 트럭에서 반복문이 종료가 된다. 그래서 마지막 트럭까지 누적된 시간과 다리의 길이를 더해서 return 하면 된다.

 

---

전체 코드

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> queue = new LinkedList<>();
        int sum = 0;
        int time = 0;

        for(int truck : truck_weights) {
            while(true) {
                if(queue.isEmpty()) {
                    queue.add(truck);
                    sum += truck;
                    time++;
                    break;
                } else if(queue.size() == bridge_length) {
                    sum -= queue.poll();
                } else  {
                    if(sum + truck <= weight) {
                        queue.add(truck);
                        sum += truck;
                        time++;
                        break;
                    } else {
                        queue.add(0);
                        time++;
                    }
                }
            }
        }

        return time + bridge_length;
    }
}