프로그래머스 | Level 2 | 다리를 지나는 트럭

Aug 31, 2024

Published byJynn

999

Programmers | Level 2 | 다리를 지나는 트럭

Problems

📘 Src: Programmers
🗂️ Cat: Simulation

󰧭 Description

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순서대로 건너려 합니다. 다리에는 트럭이 최대 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가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 반환하세요.

 Constraints

1 ≤ bridge_length ≤ 10,000
1 ≤ weight ≤ 10,000
1 ≤ truck_weights의 길이 ≤ 10,000
모든 트럭의 무게는 1 이상 weight 이하입니다.

󰦕 Examples

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

Solutions

󰘦 Code

Solution.java

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        // 다리를 지나고 있는 트럭을 저장할 큐와 트럭 무게들을 저장할 큐를 선언합니다.
        Deque<Integer> bridgeQueue = new LinkedList<>();
        Deque<Integer> truckQueue = new LinkedList<>();
        
        // 초기화: 다리 길이만큼 0을 채워서 큐를 초기화합니다.
        for (int i = 0; i < bridge_length; i++) {
            bridgeQueue.offer(0);
        }
        // 트럭 무게들을 truckQueue에 추가합니다.
        for (int truck : truck_weights) {
            truckQueue.offer(truck);
        }
        
        int elapsedTime = 0;  // 경과 시간을 기록할 변수
        int currentBridgeWeight = 0;  // 현재 다리 위의 트럭 총 무게
        
        // 트럭 대기열이 비어있지 않거나 다리 위에 트럭이 남아 있는 동안 반복합니다.
        while (!truckQueue.isEmpty() || currentBridgeWeight > 0) {
            elapsedTime++;  // 1초 증가
            
            // 다리의 앞부분(다리를 벗어난 트럭)의 무게를 빼줍니다.
            currentBridgeWeight -= bridgeQueue.poll();
            
            // 대기 중인 트럭이 없으면 다리 위에 0을 추가하고 반복문을 계속합니다.
            if (truckQueue.isEmpty()) {
                bridgeQueue.offer(0);
                continue;
            }
            
            // 대기 중인 트럭을 다리 위에 올릴 수 있는 경우
            if (currentBridgeWeight + truckQueue.peek() <= weight) {
                int incomingTruck = truckQueue.poll();  // 대기 중인 첫 트럭을 다리로 올림
                currentBridgeWeight += incomingTruck;  // 다리 위 총 무게에 추가
                bridgeQueue.offer(incomingTruck);  // 다리 큐에 트럭 추가
                continue;
            }
            
            // 다리 위에 트럭을 올릴 수 없는 경우, 0을 추가하여 트럭이 앞으로 한 칸 전진하게 합니다.
            bridgeQueue.offer(0);
        }
        
        return elapsedTime;  // 모든 트럭이 다리를 건너는 데 걸린 시간 반환
    }
}

 Approach

이 문제는 제한된 무게와 길이를 가진 다리 위를 여러 트럭이 순서대로 건널 때, 모든 트럭이 다리를 건너는 데 걸리는 최소 시간을 계산하는 문제입니다. 주어진 제약 조건을 바탕으로, 트럭들이 효율적으로 다리를 건널 수 있는 최적의 방법을 찾는 것이 핵심입니다. 이를 해결하기 위해 큐(Queue)를 사용한 시뮬레이션 접근 방식이 적합합니다.

여러 대의 트럭이 주어진 순서대로 제한된 길이와 무게를 가진 다리를 건너야 합니다. 트럭이 다리 위에 올라가면, 다리의 길이만큼 시간이 지나야 반대편으로 내려갈 수 있으며, 다리 위에 있는 트럭들의 총 무게는 다리의 최대 허용 무게를 초과할 수 없습니다. 이 문제는 선입선출(FIFO) 방식의 큐를 사용하여 트럭들이 다리를 건너는 과정을 시뮬레이션해야 합니다.

다리의 길이: 트럭이 다리 위에 머무는 시간을 결정합니다. 트럭은 다리의 길이에 따라 일정 시간 동안 다리 위에 머무르게 됩니다.
다리의 무게 제한: 다리 위에 동시에 존재할 수 있는 트럭들의 총 무게가 다리의 최대 허용 무게를 넘지 않아야 합니다.
트럭 순서: 트럭들은 주어진 순서대로 다리를 건너야 하며, 이 순서를 유지하기 위해 큐를 사용해야 합니다.

2. 접근 방식

이 문제를 해결하기 위한 주요 접근 방식은 다음과 같습니다:

큐 사용: 트럭들이 다리 위에 진입하고 이동하는 순서를 관리하기 위해 큐를 사용합니다. 큐의 길이는 다리의 길이에 대응하며, 다리 위에 트럭이 위치한 상태를 정확히 반영합니다.
트럭 대기열 처리: 트럭들이 다리 위로 올라갈 때, 다리 위의 상태와 현재 트럭들의 총 무게를 지속적으로 추적합니다. 새로운 트럭이 다리 위에 진입할 수 있는지는 다리의 무게 제한을 고려하여 결정되며, 이때 다리 위의 상태는 큐에 의해 관리됩니다.
다리 위 상태 업데이트: 매초마다 트럭이 다리 위에서 한 칸씩 이동하며, 큐의 앞부분에서 트럭이 다리 끝에 도달하면 큐에서 제거됩니다. 다리의 길이에 맞게 큐의 길이를 유지하여 트럭들이 다리 위에서 적절히 이동하는지를 시뮬레이션합니다.
경과 시간 계산: 모든 트럭이 다리를 건너는 데 걸린 시간을 1초 단위로 기록합니다. 모든 트럭이 다리를 건넜을 때, 최종적으로 경과된 시간을 반환합니다.

이 접근 방식에서 다리의 길이는 큐의 길이로 반영되며, 큐는 다리 위의 트럭들의 상태를 실시간으로 추적합니다. 이는 트럭들이 다리 위에서 정확히 이동하는지 확인하는 데 중요합니다.

다음은 주어진 예제 [7, 4, 5, 6]을 활용한 트럭 이동 과정을 시각적으로 나타낸 것입니다:

시간(초)	지나간 트럭	다리 위 상태	대기 중인 트럭
0	[]	[0, 0]	[7, 4, 5, 6]
1	[]	[0, 7]	[4, 5, 6]
2	[]	[7, 0]	[4, 5, 6]
3	[7]	[0, 4]	[5, 6]
4	[7]	[4, 5]	[6]
5	[7, 4]	[5, 0]	[6]
6	[7, 4, 5]	[0, 6]	[]
7	[7, 4, 5]	[6, 0]	[]
8	[7, 4, 5, 6]	[0, 0]	[]

이 표는 매초마다 트럭들이 다리 위를 어떻게 이동하는지를 시각적으로 보여줍니다. 최종적으로, 모든 트럭이 다리를 건너는 데 걸린 총 시간은 8초입니다. 이제 이러한 과정을 토대로 코드를 구현해보겠습니다.

3. 큐 초기화와 변수 설정

트럭의 무게를 관리하고, 매초마다 다리 위에서 트럭을 이동시키는 로직을 구현하기 위해 큐와 변수를 초기화합니다.

Solution.java

Deque<Integer> bridgeQueue = new LinkedList<>();  // 다리를 지나는 트럭을 저장할 큐
Deque<Integer> truckQueue = new LinkedList<>();   // 대기 중인 트럭들을 저장할 큐

// 다리 큐를 다리 길이만큼 0으로 초기화합니다.
for (int i = 0; i < bridge_length; i++) {
    bridgeQueue.offer(0);
}

// 트럭 큐에 모든 트럭을 추가합니다.
for (int truck : truck_weights) {
    truckQueue.offer(truck);
}

int elapsedTime = 0;  // 경과 시간을 기록할 변수
int currentBridgeWeight = 0;  // 현재 다리 위의 트럭 총 무게

bridgeQueue : 이 큐는 다리 위의 상태를 관리합니다. 다리의 길이만큼 0으로 초기화되며, 여기서 0은 다리의 빈 공간을 나타냅니다. 트럭이 다리 위로 올라갈 때 이 큐에 트럭의 무게가 추가되며, 다리 위의 상태를 실시간으로 반영합니다. 예를 들어, 다리의 길이가 3이라면 초기 상태는 [0, 0, 0]이 되며, 이후 트럭이 다리 위에 오르면 이 값들이 트럭의 무게로 갱신됩니다.
truckQueue: 이 큐는 대기 중인 트럭들을 관리합니다. 주어진 truck_weights 배열의 값을 순서대로 큐에 추가하여, 다리에 진입 대기 중인 트럭들이 차례대로 처리될 수 있도록 합니다. 트럭이 다리 위로 올라가면 이 큐에서 제거됩니다.
elapsedTime: 경과 시간을 기록하는 변수로, 트럭들이 다리를 모두 건널 때까지의 시간을 측정합니다. 각 초마다 이 변수를 1씩 증가시켜 총 경과 시간을 추적합니다.
currentBridgeWeight: 현재 다리 위에 있는 트럭들의 총 무게를 저장하는 변수입니다. 새로운 트럭이 다리 위에 올라가거나, 트럭이 다리를 완전히 건넜을 때 이 변수를 업데이트하여, 다리의 무게 제한을 초과하지 않도록 관리합니다.

4. 트럭 이동 시뮬레이션

트럭들이 다리 위로 진입하고 다리를 건너는 과정을 시뮬레이션하며, 모든 트럭이 다리를 완전히 건널 때까지의 경과 시간을 계산합니다. 이 과정은 트럭 대기열과 다리 위의 상태를 관리하면서, 매초마다 트럭들의 위치와 무게를 업데이트하는 방식으로 진행됩니다.

Solution.java

// 트럭 대기열이 비어있지 않거나 또는 다리 위에 트럭이 남아 있는 동안 반복
while (!truckQueue.isEmpty() || currentBridgeWeight > 0) {
    elapsedTime++;  // 1초 증가
    
    // 다리를 지나간 트럭의 무게를 제외합니다.
    currentBridgeWeight -= bridgeQueue.poll();
    
    // 대기 중인 트럭이 없는 경우
    if (truckQueue.isEmpty()) {
        bridgeQueue.offer(0);  // 다리 길이 유지를 위한 0 추가
        continue;  // 다음 루프를 진행
    }
    
    // 대기 중인 트럭을 다리 위에 올릴 수 있는 경우
    if (currentBridgeWeight + truckQueue.peek() <= weight) {
        int incomingTruck = truckQueue.poll();  // 대기 중인 첫 트럭을 대기열에서 제거
        currentBridgeWeight += incomingTruck;  // 다리 위 총 무게에 추가
        bridgeQueue.offer(incomingTruck);  // 다리 큐에 트럭 추가
        continue;  // 다음 루프를 진행
    }
    
    // 무게 초과로 다리 위에 트럭을 올릴 수 없는 경우
    bridgeQueue.offer(0);  // 다리 큐에 0을 추가하여 다리 위 트럭 한 칸 앞으로 전진
}

경과 시간 증가:
- 매 루프가 시작될 때마다 경과 시간을 1초씩 증가시킵니다.
- 이 시간은 트럭들이 다리를 모두 건널 때까지의 총 시간을 추적하는 데 사용됩니다.
다리를 지난 트럭 처리:
- 매 루프마다 bridgeQueue에서 트럭(또는 빈 공간)을 한 칸 제거(poll())합니다.
- 제거된 요소가 트럭의 무게인 경우, 해당 무게를 currentBridgeWeight에서 차감하여 현재 다리 위의 총 무게를 갱신합니다. 이는 트럭이 다리 끝에 도달하여 다리를 벗어나는 상황을 나타냅니다.
대기 중인 트럭이 없을 때:
- 만약 대기 중인 트럭이 없다면, 다리 위의 상태를 유지하기 위해 bridgeQueue에 0을 추가하고, 다음 루프를 진행합니다.
- 이렇게 bridgeQueue의 마지막에 0을 추가하는 것은, 트럭들이 한 칸씩 앞으로 이동하는 것을 표현한 것입니다.
대기 중인 트럭이 있을 때:
- 대기 중인 트럭이 있고, 다리 위의 현재 무게와 대기 중인 트럭의 무게를 합한 값이 다리의 허용 무게를 초과하지 않는 경우, 해당 트럭을 truckQueue에서 제거하여 다리 위로 올립니다.
- 이때, 트럭의 무게를 currentBridgeWeight에 더하고, bridgeQueue에 트럭의 무게를 추가하여 다리 위 상태를 갱신합니다.
다리 위 무게 초과로 트럭을 올릴 수 없을 때:
- 대기 중인 트럭이 있지만, 다리 위로 진입할 수 없는 경우, bridgeQueue에 0을 추가하고 다음 루프로 넘어갑니다.
- 이로써 다리 위의 상태를 유지하며, 다음 루프에서 트럭을 올릴 수 있는지 다시 확인합니다.

이렇게 다리 위 상태를 매초 업데이트하면서, 모든 트럭이 다리를 건널 때까지의 시간을 계산합니다.

5. 결과 반환

모든 트럭이 다리를 건너고 더 이상 다리 위에 트럭이 없으면, 최종적으로 경과된 시간을 반환합니다.

Solution.java

// 모든 트럭이 다리를 건너는 데 걸린 시간 반환
return elapsedTime;

󰄉 Complexity

⏳ TC: O(n)
💾 SC: O(n)

트럭의 수를 n이라고 할 때, 모든 트럭이 다리를 건너기까지의 시뮬레이션은 최대 n번의 연산을 필요로 하므로 시간 복잡도는 O(n)입니다. 또한, 다리와 트럭을 관리하기 위한 큐의 공간이 필요하므로 공간 복잡도도 O(n)입니다.

이 알고리즘은 다리를 건너는 트럭의 순서와 무게 제한을 고려하여 효율적으로 문제를 해결합니다. 각 단계에서 트럭이 다리에 올라가거나 대기하도록 하는 과정이 핵심입니다.

Algorithm
Simulation