[Programmers] 다리를 지나는 트럭 (Java)

다리를 지나는 트럭 

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

대기하는 트럭 리스트(값은 트럭의 무게)가 주어지고, 리스트에 있는 트럭이 다리를 모두 지나는 시간을 리턴하는 문제이다.

 

• 단, 다리를 지날 때 다리 위에 있는 트럭들의 무게 합산이 다리가 버틸 수 있는 무게(weight) 보다 적어야 하고
• 하나의 트럭이 다리를 지나는 시간은 bridge_length 와 같다.

큐와 스택 카테고리에 있어서, 큐로 풀었다. (구현체는 deque 쓰긴 함)

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> bridge = new ArrayDeque<>();

		// 다리 길이 만큼의 큐 생성
        // 시간 값은 한번 이동할 때 1초 라고 명시 되어 있다.
        for (int i = 0; i < bridge_length - 1; i++) {
       		// 처음에 다리는 전부 비어 있다. (0이 비어 있음을 의미)
            // bridge_length -1 미만을 도는 이유는 0번째 트럭은 무조건 다리 위에 올 것이기 때문에
       		bridge.add(0);
        }
        
        // 0번째 트럭은 무조건 다리 위에 있을 것이다. (하나의 트럭 무게가 weight 보다 큰 경우는 없을 것)
        int currentWeights = truck_weights[0];
        bridge.add(currentWeights);
        // 현재 다리 위에 있는 트럭은 0 이고 다음에 올 트럭이 1이다.
        int index = 1;
        // 다리 위에 0번째 트럭이 올라갔기 때문에 1부터 시작 (0초가 지남)
        int answer = 1

		// 다리에 트럭이 있는 경우
        while (!bridge.isEmpty()) {
            // 시간 증가
            answer++;
            // 다리 위에 있는 첫번째 트럭이 빠진다.
            // 다리 위에 트럭이 없으면 이 값은 0일 것이다.
            int truck = bridge.poll();
            // 다리 위의 첫번째 트럭이 빠졌기 때문에
            // 현재 다리 위에 모든 트럭의 무게에서 첫번째 트럭의 무게를 빼준다.
            currentWeights -= truck;
            // 대기하는 트럭이 남아 있다면
            if (index < truck_weights.length) {
            	// 현재 무게 + 대기하는 첫번째 트럭의 무게가 weight 보다 작은 경우
                // 다음 트럭 (대기하는 첫번째 트럭) 은 다리 위에 올 수 있다.
                if (currentWeights + truck_weights[index] <= weight) {
                	// 다음 트럭이 다리 위에 온다.
                    currentWeights += truck_weights[index];
                 	// index 를 증가시켜 다음에 올 트럭을 지정한다.
                    bridge.add(truck_weights[index++]);
                } else {
                	// 다리 위에 있는 트럭이 앞으로 이동한다. (대기하는 트럭은 다리 위에 오지 못한다.)
                    // 다리 위에 새 트럭은 오지 않는다. (0은 트럭이 없음을 의미)
                    bridge.add(0);
                }
            }
        }
        return answer;
    }
}

 

다리 길이 만큼의 큐를 만들었고, 큐에는 다리를 건너는 트럭들이 담겨 있다.

트럭의 무게는 최소 1 이상이므로 트럭이 없는 경우는 0과 같다. (그래서 0 으로 초기화를 해 주었다.)

 

트럭이 다리를 모두 건넜다는 이야기는 하나의 트럭 A 가 큐에 들어가고, 나올 때 까지와 같다. 

또한 트럭이 이동하는 시간은 1초에 1만큼 움직이기 때문에, 하나의 트럭 A 가 큐에 들어가고 나올 때 까지의 loop 문이 도는 횟수가 트럭 A 가 다리를 모두 건너는 시간과 동일하다고 보면 된다.

 

첫 번째 예제로 보면

2 (다리 길이)

10 (다리가 견디는 무게)

[7,4,5,6] (건널 트럭 목록)

우선 첫 번째 트럭 (0 번째 인덱스) 은 무조건 0 초 때 다리에 올라오게 된다. (조건에서 모든 트럭의 무게는 weight 이하라고 봤기 때문이다.)

 

그래서 큐 bridge 에 첫 번째 트럭을 넣어주고, 현재 다리의 무게를 currentWeights 로 맞춰 주었다.

첫 번째 트럭이 다리위에 올라왔기 때문에 이미 시간은 1초 지났다고 보았다. 그래서 answer 를 1로 두었고 다음에 지나갈 트럭을 위해 index 도 1로 두었다.

 

이후엔 다리가 빌 때 까지, 즉 모든 트럭이 다리를 건널 때 까지 반복문을 돌아준다.

 

반복문을 돌 때 예제로 보면 bridge = [0, 7], index = 1, answer = 1 인 상태가 된다.

0 번째 (무게 7인) 트럭이 1초 동안 1만큼 움직이기 때문에 answer 를 1로 증가 시키고, brdige 에서 pop 을 했다. (큐는 FIFO 이기 때문에 먼저 들어간 트럭이 먼저 나온다. 트럭이 1만큼 이동했다고 보면 된다.)

 

pop 해서 나온 값은 트럭의 무게와 같고 이를 현재 무게에서 빼면 트럭 하나가 다리를 다 건넜다고 볼 수 있다.

 

현재 큐에는 [0, 7] 이 들어있기 때문에 전체 currentWeights 는 변화가 없다. (큐는 [7] 이 된다.)

결국 다음에 올 2번 째 트럭 (1번 인덱스) 무게 4는 다리위에 올 수가 없다.

 

조건에서는 else 문에 걸리고, 트럭은 다리위에 못 오고, 이미 있는 트럭 (0번째 인덱스) 만 움직였다.

그래서 트럭이 없다는 의미인 0을 큐에 추가한다. 이럴 경우 이미 있는 값은 앞으로 이동한다. (FIFO)

 

이런식으로 계속 진행 하면 된다.

 

중요한 것은 트럭이 다리 위에 있다는 것을 큐로 표기했다는 것 (먼저 들어간 트럭이 먼저 나온다.)

그리고 다리를 의미한 큐에 트럭이 없다는 의미를 0으로 표기했다는 것 이다.

 

이후에, 다리를 건널 수 있다 없다 는 단순한 if-else 문 이여서 구현만 하면 된다.