6. 프로그래머스 - 다리를 지나는 트럭(큐)

문제 설명: 다리를 지나는 트럭

 

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순서대로 지나가려고 합니다.
이때 다리는 다음과 같은 제약 조건을 가집니다:

• 동시에 올라갈 수 있는 트럭 수는 최대 bridge_length대입니다.
• 동시에 버틸 수 있는 최대 무게는 weight입니다.
• 트럭은 1초에 한 칸씩 전진하며, 다리를 완전히 지나기 위해서는 bridge_length초가 걸립니다.
• 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

트럭들은 주어진 순서대로만 다리를 건널 수 있습니다.
모든 트럭이 다리를 건너는 데 최소 몇 초가 걸리는지 구하세요.

 

입력 형식

다음 세 개의 인자가 함수의 매개변수로 주어집니다.

int bridge_length // 다리의 길이 (다리 위에 동시에 올라갈 수 있는 최대 트럭 수)

int weight // 다리가 견딜 수 있는 최대 무게

int[] truck_weights // 트럭들의 무게 배열 (순서대로 다리를 건넘)

 

 

제한 조건

• 1 ≤ bridge_length ≤ 10,000
• 1 ≤ weight ≤ 10,000
• 1 ≤ truck_weights.length ≤ 10,000
• 각 트럭의 무게는 1 이상 weight 이하입니다.

 

출력 형식

모든 트럭이 다리를 건너는 데 걸리는 최소 시간(초)을 반환합니다.

int result // 최소 시간 (초)

 

 

입출력 예시

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

 

 

예시 1

다리 길이: 2, 최대 하중: 10
트럭 무게: [7, 4, 5, 6]

시뮬레이션:

시간다리를 지난 트럭다리 위 트럭대기 중 트럭

0	[]	[]	[7, 4, 5, 6]
1	[]	[7]	[4, 5, 6]
2	[]	[7, 0]	[4, 5, 6]
3	[7]	[4]	[5, 6]
4	[7]	[4, 5]	[6]
5	[7, 4]	[5, 0]	[6]
6	[7, 4, 5]	[6]	[]
7	[7, 4, 5]	[6, 0]	[]
8	[7, 4, 5, 6]	[]	[]

 

---

알고리즘 코드

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

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> bridge = new ArrayDeque<>();
        
        int sumWeight = 0;
        int time = 0;
        
        for(int truckWeight : truck_weights) {
            while(true) {
                if(bridge.isEmpty()) { // 다리가 빈 경우
                    bridge.add(truckWeight);
                    sumWeight += truckWeight;
                    time++;
                    break;
                }else if(bridge.size() == bridge_length) { 
                // 다리에 올라와 있는 트럭의 개수와 다리에 있는 트럭 개수가 같은 경우
                // 이미 다리 끝에 있는 트럭이 존재하므로 빼주면 됨
                    sumWeight -= bridge.poll();        
                }else { // 다리에 트럭이 하나라도 올라와 있는 경우
                    if(sumWeight + truckWeight <= weight) { // 다리에 있는 트럭의 합과
                    // 이제 다리를 지나려는 트럭의 합이 다리가 견딜 수 있는 무게보다 작거나 같은 경우
                        bridge.add(truckWeight);
                        sumWeight += truckWeight;
                        time++;
                        break;
                    }else { // 아닌 경우 0을 추가해서 앞으로 한 칸씩 트럭을 이동
                        bridge.add(0);
                        time++;
                    }
                }
            }
        }
        return time +  bridge_length; // 마지막 트럭이 건너는 시간까지 고려
    }
}

 

시간 복잡도 분석

다리 위 상태를 저장하는 bridge_length의 최대 길이 이므로 O(N)이다.