[프로그래머스] 다리를 지나는 트럭 문제 (Java Queue 풀이)

안녕하세요, 스코리아입니다.

오늘은 자바(Java)의 Queue를 이용한 프로그래머스 Lv.2 다리를 지나는 트럭 문제를 풀어보겠습니다.

문제가 Queue를 사용하기에 너무 적합하고 깔끔한 문제라 가져와 보았습니다.

 

문제 설명

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

프로그래머스

• 트럭은 한 번에 1만큼의 거리를 이동할 수 있습니다. 즉, 트럭 한 대가 길이 bridge_length의 다리를 건너기 위해서는 bridge_length만큼의 시간이 필요합니다.
• 트럭의 크기는 1입니다. 즉, 길이 bridge_length인 다리 위에 올라갈 수 있는 트럭의 수는 최대 bridge_length 대입니다.
• 다리는 '일 차선 다리'입니다. 한 번에 한대의 트럭밖에 건널 수 없습니다.
• 모든 트럭이 다리를 건넜다는 것은 다리 위에 트럭이 한대도 남아있지 않음을 뜻합니다.
• 한 트럭이 빠져나감과 동시에 다른 트럭이 다리 위에 올라올 수 있습니다. 다리가 견딜 수 있는 최대 weight만 잘 고려하면 됩니다.

프로그래머스 문제 - 다리를 지나는 트럭

트럭이 나가고 들어오는 과정이 유기적으로 필요하기 때문에 자바의 Queue 구조를 이용하면 비교적 간단하게 풀 수 있습니다.

문제에 나와있는 예시를 토대로 설명해 보겠습니다.

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

• 우선 bridge_length가 2이기 때문에 다리 위에는 최대 2개의 트럭밖에 오지 못합니다.
• 초기(1초가 되는 시점)에 트럭이 한 대 올라가 있어야 하므로, queue 값을 0 7로 세팅하고 시작하겠습니다.
• 여기서 0은 무게 0kg , 7은 트럭 무게 7kg을 뜻합니다. 즉, 0은 트럭이 없는 곳을 뜻합니다.
• 다리가 버틸 수 있는 최대 무게 weight는 10이라고 합니다.

트럭이 오른쪽에서 들어와서, 트럭이 왼쪽으로 한 칸씩 이동하여 다리를 빠져나간다고 생각하면 이해하기 편합니다.

1. [1초] 0 7 (다리 위에 7kg 트럭이 진입한 상태)
2. [2초] 7 0 (7kg 트럭이 다리 한 칸 앞으로 감. 단, 다음 트럭이 4kg이므로 동시에 올라올 수 없음. 7 + 4 > 10)
3. [3초] 0 4 (7kg 트럭이 빠지고 4kg 트럭이 올라옴)
4. [4초] 4 5 (4kg 트럭이 다리 한 칸 앞으로 감. 다음 트럭이 5kg이므로 동시에 올라올 수 있음. 4 + 5 < 10)
5. [5초] 5 0 (4kg 트럭이 빠지고 5kg 트럭이 다리 한 칸 앞으로 감. 다음 트럭이 6kg이므로 동시에 올라올 수 없음. 5 + 6 > 11)
6. [6초] 0 6 (5kg 트럭이 빠지고 6kg 트럭이 올라옴)
7. [7초] 6 (6kg 트럭이 다리 한칸 앞으로 감. 다음 트럭이 없음)
8. [8초] (6kg 트럭이 빠짐. 다리 위가 비었음 => 종료)

 

여기서 중요한 점은, 트럭이 없는 곳은 0kg으로 설정해주어야 한다는 것입니다. 단, 와야 할 '다음 트럭'이 없을 경우, 0을 넣지 않습니다. 그래야 다리에 모든 트럭이 빠져나갔는지 (queue가 비었는지) 확인할 수 있습니다.

 

 

풀이 과정

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
    	Queue q = new LinkedList();
        
        // 0번째 트럭을 올릴거기 때문에 bridge_length - 1 만큼 0으로 채워줌
        for(int i=0;i<bridge_length-1;i++){
            q.add(0);
        }
        
        // 현재 다리에 있는 트럭 무게
        int current_w = truck_weights[0];
        // 0번째 트럭을 다리 위에 올리기
        q.add(current_w);
        
        int answer = 1; // 0번째 트럭이 이미 올라갔으므로 시간 1부터 시작
        int index = 1; // 0번째 트럭이 이미 올라갔으므로 다음 트럭 index는 1부터 시작
        
        while(!q.isEmpty()){
            answer++; // 시간 1 증가
            
            int removed = (int) q.poll(); // 빠져나갈 트럭 1대 제거
            current_w -= removed; // 현재 다리의 트럭무게에서 제거된 트럭 무게 제거

		// 남은 트럭이 존재할 경우 (올라가야할 트럭이 남아있을 경우)
            if(index < truck_weights.length){
            	// 현재 다리에 있는 트럭무게 + 다음에 올라갈 트럭 무게 <= 다리가 버틸 수 있는 무게
                if(current_w + truck_weights[index] <= weight){
                    current_w += truck_weights[index]; // 다음 트럭 무게 추가
                    q.add(truck_weights[index]); // queue 에 다음 트럭 추가
                    index++; // index 증가
                }else{
                    q.add(0); // 다음 트럭이 오지 못했으므로, 0 추가 (다음 트럭이 다음번에 와야하므로)
                }
            }
        }
        
        return answer;
    }
}

1. q 이름을 가진 Queue를 만들어줍니다.
2. 처음 1 시간에는 0번째 트럭이 무조건 올라가 있어야 합니다. 그러므로, queue에 bridge_legnth-1만큼 0으로 채워 넣고, 0번째 트럭의 무게를 queue에 넣습니다.
3. current_w 변수는 현재 다리에 있는 트럭들의 총무게를 뜻합니다. 현재 0번째 트럭이 올라가 있으므로, current_w는 0번째 트럭의 무게입니다.
4. answer 변수는 시간(초)을 뜻합니다. 현재 0번째 트럭이 올라가 있으므로, 시간이 1인 상태입니다.
5. index 변수는 다음 트럭 무게(truck_weights)의 index를 뜻합니다. 현재 0번째 트럭이 올라가 있으므로, 다음 트럭 무게의 index는 1번째 트럭입니다.
6. Queue에 값이 없으면 모든 트럭이 다리를 건너서, 다리에 아무 트럭도 없는 상태를 뜻합니다. 그러므로 q가 비어있지 않을 때까지 while 문을 돌립니다.

 

[While문 풀이]

1. Queue의 poll을 이용하여 맨 앞에 있는(빠져나갈) 트럭(혹은 0kg 무게)을 제거합니다. 이런 행동은 1의 시간이 소비됩니다. 그러므로 answer에 1만큼 더합니다.
2. 현재 다리의 트럭 무게(current_w)에서 방금 제거된 트럭 무게(removed)를 빼줍니다.

남은 트럭이 존재할 경우. 즉 올라가야 할 트럭이 남아있는 경우 (If문)

1. " 현재 다리에 있는 트럭 무게(current_w) + 다음에 올라가야 할 트럭 무게 (truck_weights[index]) <= 다리가 버틸 수 있는 무게 " 조건이 만족되는 경우 다음 트럭이 들어올 수 있습니다. 만족하는 경우, 다음 트럭 무게를 current_w 변수에 추가하고, queue에 다음 트럭 무게를 추가합니다. 그리고 다음 트럭 무게의 index의 값을 1만큼 증가시킵니다.
2. 조건이 만족하지 않은 경우, 다음 트럭이 들어오지 못함을 뜻합니다. 즉, 다음번에 트럭이 와야 할 일이 있으므로, Queue에 0을 추가해 줍니다.

위쪽의 예시에서 알아봤듯이, 이 while문을 통해 Queue에 아무 값도 없을 때까지 반복한다면, 다리에 아무 트럭이 없으면 while 문이 종료되어, 얼마나 시간이 걸렸는지 answer 값을 파악할 수 있습니다.

 

 

실행 결과

프로그래머스 문제 실행결과 - 다리를 지나는 트럭

• 대부분의 테스트는 0~1ms 정도의 빠른 속도를 보여줍니다. 다만 일부 테스트는 13ms, 43ms처럼 튀는 곳도 있습니다.
• 다른 분들의 풀이를 보니, 1초일 때의 초기값을 설정하지 않고, for문 안에 while문을 사용하여 풀이하신 모습을 보았습니다. 이럴 경우 조금 더 느린 속도를 보여줍니다.

 

---

지금까지 자바(Java)의 Queue를 활용한 프로그래머스 '다리를 지나는 트럭' 문제에 대해서 알아보았습니다.

읽어주셔서 감사합니다.