[프로그래머스 / Level2] 다리를 지나는 트럭 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/42583?language=java 

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

 

풀이

• 다리에는 최대 bridge_length 대의 트럭이 올라갈 수 있으며, 올라간 트럭들의 무게는 weight이하여야 한다.
• 하나의 트럭이 다리를 완전히 지나는데 bridge_length 만큼 시간이 걸린다.
• 트럭이 다리위에서 움직일 때마다 1초가 지난다.
• 1초가 지날때마다 모든 트럭은 한칸씩 움직인다.
• 다리 위에 있는 트럭의 수가 bridge_length와 같을 경우 가장 먼저 들어온 트럭이 다리 밖으로 나가게 된다.
• 중간까지는 앞 트럭이 다리를 다 지나는 순간 바로 뒤 트럭이 다리에 들어오지만, 마지막에는 '모든 트럭이 전부 다리를 지나서 다리위에 트럭이 하나도 없는 상태'가 되기까지의 시간을 반환해야 한다.

 

'다리를 지나는 중인 트럭' 목록은 먼저 들어온 것이 먼저 나가는 구조여야 하기 때문에 Queue를 사용한다.
처음에는 아래와 같이 Truck 클래스를 만든 뒤 Truck객체를 Queue에 넣는 식으로 생각했으나 그러면 1초마다 Queue내의 객체들에 대해 하나씩 조건을 파악해야 되므로 비효율적이라 판단했다.

class Truck {
    boolean passBridge  // 다리를 지났는지 여부
    int weight;         // 트럭 무게  
    int time;           // 경과 시간
}

 

1. truck_weights에 있는 트럭들을 일단 전부 다리에 올려야하기 때문에 각 요소를 '다리에 올리는 작업'을 반복한다.

for (int truck_weight : truck_weights) { }

 

2. 그런데 새 트럭을 다리에 올리려는데, 앞 트럭들의 무게만으로도 weight무게 제한을 초과할 경우는 새 트럭을 올릴 수 없다. 이럴 때는 새 트럭을 올리지 않고 기존의 트럭들만을 이동시켜야 하는데 얼마나 이동시켜야 새 트럭이 들어갈만한 여유 무게가 남아날지 알 수 없기 때문에 '새 트럭이 다리위에 올라갈 때까지' 위 과정을 무한 반복해야 한다.

for (int truck_weight : truck_weights) { 
    while(true) {
         // 새 트럭(truck_weight) 올리기 or 다리 위 트럭들 이동시키기
    }
}

 

3. 트럭을 다리에 올릴 수 있는 경우는 아래 3가지 이다.

• 다리가 비어 있을 경우
• 다리가 다 차 있으면서, 맨 앞의 트럭이 빠졌을 때 새 트럭이 들어가도 무게제한에 걸리지 않을 경우
• 다리가 다 차 있지는 않으면서, 새 트럭이 들어가도 무게제한에 걸리지 않을 경우

위 경우에만 새 트럭(truck_weight : 새 트럭 무게)을 추가하고, 나머지 경우에는 빈공간(0)을 추가해서 앞 트럭들을 한 칸씩 이동시킨다. 이때 무게제한 비교용으로 '현재 다리위에 있는 트럭들의 총 무게' 값을 저장해둬야 하기 때문에 다리위에 트럭이 올라가거나 빠질때 sum값을 그 만큼 증가하거나 감소시켜줘야 한다.

 

4. 다리 위를 지나는 트럭 상황에 변화가 생길 때마다 time 시간을 1씩 늘려준다. 그러나, for문은 '트럭을 다리위에 올리는 작업'만을 반복하기 때문에 이 반복문에서 누적된 시간은 '마지막 트럭을 다리위에 올리기까지 걸리는 시간'이다. 문제에서는 모든 트럭이 다리 위를 지나기 까지 걸리는 시간이므로 여기에 다리의 전체 길이인 bridge_length 값을 추가해줘서 '마지막 트럭이 다리위를 지나는데 걸리는 시간'을 추가해줘야 한다.

모든 트럭이 다리를 지나는데 걸리는 시간
= 마지막 트럭을 다리 위에 올리는데 걸리는 시간 + 마지막 트럭이 다리 위를 지나는데 걸리는 시간

 

코드

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

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;   // 시간
        int sum = 0;    // 다리위에 있는 트럭의 총 무게

        Queue<Integer> queue = new LinkedList<>();     // 다리

        for (int truck_weight : truck_weights) {
            // 해당 트럭이 들어가려면 앞 트럭들이 빠질때까지 기다려야하기 때문에, 현재 트럭이 들어갈 때까지 무한 반복
            while (true) {
                if (queue.isEmpty()) {                        // 다리가 비어 있을 경우
                    queue.add(truck_weight);
                    sum += truck_weight;
                    time++;
                    break;
                } else if (queue.size() == bridge_length) {   // 다리가 다 차 있을 경우
                    int truck = queue.poll();
                    sum -= truck;
                    time++;
                    if (sum + truck_weight <= weight) {       // 현재 트럭이 들어가도 무게제한 안 걸릴 경우
                        queue.add(truck_weight);
                        sum += truck_weight;
                        break;
                    } else {
                        queue.add(0);
                    }
                } else {                                      // 다리가 다 차지는 않았을 경우
                    time++;
                    if (sum + truck_weight <= weight) {
                        queue.add(truck_weight);
                        sum += truck_weight;
                        break;
                    } else {
                        queue.add(0);
                    }
                }
            }
        }

        return time + bridge_length;        // 마지막으로 들어간 트럭이 다리를 지날 시간 추가
    }
}

 

트럭이 다리를 지나는 과정을 확인하고 싶을 때는 각 if~else 문들에 아래 코드를 넣어 현재 Queue에 저장되어 있는 트럭 무게를 출력하도록 한다.

System.out.println(time + ": " + queue);

 

[테스트케이스 3]

bridge_length	weight	truck_weights	return
100	100	[10,10,10,10,10,10,10,10,10,10]	110

[실행 과정]

0: []
1: [10]
2: [10, 10]
3: [10, 10, 10]
4: [10, 10, 10, 10]
5: [10, 10, 10, 10, 10]
6: [10, 10, 10, 10, 10, 10]
7: [10, 10, 10, 10, 10, 10, 10]
8: [10, 10, 10, 10, 10, 10, 10, 10]
9: [10, 10, 10, 10, 10, 10, 10, 10, 10]
10: [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
110

1초~10초 동안 트럭 10개가 다리위로 올라가고, 마지막 트럭이 다리 100칸을 완전히 지나는데 100초가 허비된다. (10 + 100 = 110), 100초 동안은 새로 올라오는 트럭은 없이 이미 다리위에 올라가 있는 트럭들이 이동하기만 한다.