[프로그래머스] Java Lv2. 코딩테스트 연습 > 스택/큐 > 다리를 지나는 트럭 42583

문제설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

접근방법

1. 다리에 먼저 접근한 차량이 먼저 빠져나가니 Queue를 선택.
2. 시간을 증가시키며 다리(큐)에 차량을 집어넣는 방법으로 접근.
3. 다리에 들어간 차량의 시간을 알아야 빠져나오는 시간이 계산 가능하므로 큐에는 차량의 시간 정보를 입력
4. 들어간 마지막 차량의 index를 변수에 집어넣고, 빠져나온 차량의 index는 큐의 size로 계산

핵심로직

1. while문을 사용하여 시간(answer)을 계속해서 증가 시키며 로직 진행 : 시간복잡도 O(n)
2. 큐의 맨 앞 시간에 다리 길이(빠져나오는 시간)를 합친 값이 현재 시간(answer)보다 작거나 같으면 큐에서 제거 및 무게 감소
3. 다리에 다음 차량이 들어갈 수 있는 상황이면 현재 시간(answer) 입력 및 index +1

입출력 예

• bridge_length = 2
• weight = 100
• truck_wieghts = [7, 4, 5, 6]
• return = 8

코드 작성(1차)

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        // 현재 다리에 올라간 트럭들의 진입 시간을 저장하는 큐
        Queue<Integer> onBridgeTime = new LinkedList<>();
        
        // 다리를 건너는 데 걸린 총 시간
        int answer = 0;
        
        // 현재 다리 위에 있는 트럭들의 총 무게
        int weightSum = 0;
        
        // truck_weights 배열을 탐색하기 위한 인덱스
        int index = 0;
        
        // 트럭이 모두 다리를 건널 때까지 반복
        while(index < truck_weights.length) {
            answer++; // 시간 경과

            // 다리 위에 트럭이 있고, 다리의 맨 앞 트럭이 다리를 다 건넌 경우
            if (!onBridgeTime.isEmpty() && onBridgeTime.peek() + bridge_length <= answer) {
                // 다리에서 트럭을 내리며, 그 트럭의 무게를 다리 무게에서 빼줌
                weightSum -= truck_weights[index - onBridgeTime.size()];
                onBridgeTime.poll(); // 다리 큐에서 해당 트럭을 제거
            }

            // 다리에 트럭을 추가할 수 있는지 확인
            if (onBridgeTime.size() < bridge_length && weightSum + truck_weights[index] <= weight) {
                // 트럭을 다리에 추가하며 진입 시간 기록
                onBridgeTime.add(answer);
                
                // 다리 위 트럭들의 총 무게 업데이트
                weightSum += truck_weights[index];
                
                // 다음 트럭으로 이동
                index++;
            }
        }

        // 마지막 트럭이 다리를 완전히 건너는 데 필요한 시간 추가
        answer += bridge_length;
        
        return answer; // 모든 트럭이 다리를 건너는 데 걸린 총 시간 반환
    }
}

큐에 시간 정보가 들어간다는 것이 직관적이지 않으니 큐에 차량 무게를 집어넣기 위해선 어떻게 하면 될까?

매 시간마다 큐에 차량 무게(차량이 안들어가는 경우 0)를 집어넣으며 처리 가능

코드 작성(2차)

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
       Queue<Integer> bridge = new LinkedList<>();
        int answer = 0; // 경과 시간
        int weightSum = 0; // 다리 위의 총 무게
        int index = 0; // truck_weights 인덱스

        // 다리 길이만큼 0으로 초기화하여 트럭이 없는 상태를 나타냄
        for (int i = 0; i < bridge_length; i++) {
            bridge.add(0);
        }

        while (index < truck_weights.length) {
            answer++; // 시간 증가

            // 다리 앞에서 나오는 트럭의 무게를 다리에서 빼줌
            weightSum -= bridge.poll();

            // 다음 트럭이 다리에 올라갈 수 있는지 확인
            if (weightSum + truck_weights[index] <= weight) {
                bridge.add(truck_weights[index]);
                weightSum += truck_weights[index];
                index++;
            } else {
                // 무게 초과 시 0을 추가하여 다리 길이 확보
                bridge.add(0);
            }
        }

        // 마지막 트럭이 다리를 완전히 건너기 위한 시간 추가
        answer += bridge_length;

        return answer;
    }
}