[프로그래머스] 다리를 지나는 트럭 - Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

---

 

문제 개요

트럭들이 순서대로 일차선 다리를 건너려 합니다. 다리는 최대 bridge_length대의 트럭을 동시에 수용할 수 있으며, 총 무게 weight만큼의 하중을 견딜 수 있습니다. 모든 트럭이 대기열 순서대로 다리를 건널 때 필요한 최소 시간을 구하는 문제입니다.

 

문제 풀이 개요

각 트럭이 다리를 건너는 상황을 시뮬레이션하여 풀이합니다. 다리를 건너는 트럭들을 큐에 저장하며 트럭이 다리를 통과할 때마다 시간을 증가시키고, 새로운 트럭이 올라갈 수 있는지를 계산합니다. 무게 제한을 초과하는 경우, 트럭 대신 빈 자리를 큐에 넣어 다리가 차 있는 상태를 유지합니다.

 

해결 과정

1. 다리 상태를 큐로 표현하기
   • bridge_length의 크기를 가지는 큐를 생성해 다리 위의 트럭을 관리합니다. 각 트럭이 다리를 건너기 시작할 때 큐에 추가되며, 시간이 지남에 따라 다리를 통과한 트럭은 큐에서 빠져나갑니다.
2. 트럭 이동 시뮬레이션
   • truck_weights의 트럭을 순서대로 큐에 추가해 이동을 시뮬레이션합니다.
   • curW 변수를 통해 다리 위 트럭들의 현재 무게를 추적하며 새로운 트럭이 다리에 오를 수 있는지를 확인합니다. 트럭이 다리에 올라가면 curW에 해당 트럭의 무게를 더하고, 다리를 건너는 데 걸리는 시간을 증가시킵니다.
3. 무게 초과 처리
   • 다리 위 트럭의 무게와 새로운 트럭의 무게 합이 weight를 초과할 경우, 현재 트럭을 다리에 올릴 수 없으므로 큐에 0을 추가하여 대기합니다.
4. 모든 트럭이 다리를 건넌 후 추가 시간 계산
   • 모든 트럭이 다리에 올라간 후 다리를 완전히 빠져나가려면 bridge_length만큼의 시간이 더 필요합니다. 따라서 전체 시간을 계산할 때 마지막으로 트럭이 다리를 다 건너는 시간을 더합니다.

 

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Queue<Integer> q = new LinkedList<>();

        // 다리 길이만큼 0으로 초기화하여 대기열을 표현
        for(int i = 0; i < bridge_length; i++) {
            q.add(0);
        }

        int idx = 0;    // 대기 중인 트럭의 인덱스
        int curW = 0;   // 현재 다리 위 트럭들의 무게 합

        // 모든 트럭이 다리를 건널 때까지 반복
        while (idx < truck_weights.length) {
            // 다리를 다 건넌 트럭 무게 빼기
            curW -= q.poll();
            answer++;

            // 다음 트럭을 다리에 올릴 수 있는지 확인
            if (curW + truck_weights[idx] <= weight) {
                q.add(truck_weights[idx]);
                curW += truck_weights[idx];
                idx++;  // 다음 트럭으로 이동
            } else {
                q.add(0);  // 무게 초과 시 빈 공간 유지
            }
        }

        // 마지막 트럭이 다리를 완전히 건너는 시간 추가
        return answer + bridge_length;
    }
}