스텍 / 큐 : 다리를 지나는 트럭

문제 이해

트럭 여러 대가 일차선 다리를 건너려고 한다. 다리에는 무게 제한과 길이 제한이 있어서, 모든 트럭이 안전하게 건너는 데 걸리는 최소 시간을 구해야 한다.

문제 조건

• bridge_length: 다리 길이 (트럭이 다리를 건드는 데 걸리는 시간)
• weight: 다리가 견딜 수 있는 최대 무게
• truck_weights: 트럭들의 무게 배열 (순서대로 출발)

핵심 규칙

1. 트럭들은 주어진 순서대로만 출발 가능 (새치기 불가)
2. 모든 트럭의 속도는 동일 (1초에 1칸)
3. 다리 위 트럭들의 총 무게 ≤ weight 조건 유지
4. 트럭은 다리에 동시에 여러 대 있을 수 있음

 

첫 번째 버전: 클래스 + 큐 2개 사용

class Truck {
    int weight;
    int exitTime;
    
    Truck(int weight, int exitTime) {
        this.weight = weight;
        this.exitTime = exitTime;
    }
}

Queue<Integer> waitingQueue = new LinkedList<>();
Queue<Truck> bridgeQueue = new LinkedList<>();

 

두 번째 버전: 큐 안에 정수형 배열로 관리

import java.util.*;

class Solution {
   public int solution(int bridge_length, int weight, int[] truck_weights) {
       Queue<int[]> bridge = new LinkedList<>(); // [무게, 나가는시간]
       int index = 0; // 다음에 출발할 트럭 인덱스
       int time = 0;
       int currentWeight = 0; // 다리 위 트럭들의 총 무게
       
       while (index < truck_weights.length || !bridge.isEmpty()) {
           time++;
           
           // 1. 다리에서 나갈 트럭들 제거
           while (!bridge.isEmpty() && bridge.peek()[1] == time) {
               int[] exitTruck = bridge.poll();
               currentWeight -= exitTruck[0];
           }
           
           // 2. 새 트럭이 들어갈 수 있는지 체크
           if (index < truck_weights.length) {
               int nextTruckWeight = truck_weights[index];
               if (currentWeight + nextTruckWeight <= weight) {
                   // 새 트럭 출발
                   bridge.offer(new int[]{nextTruckWeight, time + bridge_length});
                   currentWeight += nextTruckWeight;
                   index++;
               }
           }
       }
       
       return time;
   }
}

 

장단점 비교

첫 번째 버전의 장점

• 가독성: truck.weight, truck.exitTime으로 명확한 의미 전달
• 타입 안정성: 컴파일 타임에 오류 검출 가능
• 객체지향적: 데이터와 관련된 로직을 묶어서 관리 가능

첫 번째 버전의 단점

• 메모리 오버헤드: 객체 생성 비용, 추가 클래스 정의 필요
• 코드 복잡성: 클래스 정의 + 큐 2개 관리
• 성능: 객체 생성/소멸로 인한 GC 부담

 

두 번째 버전의 장점

• 메모리 효율성: 기본 타입 배열 사용으로 메모리 절약
• 코드 간결성: 클래스 정의 불필요, 큐 1개로 관리
• 성능: 객체 생성 비용 절약
• 구현 단순성: 로직이 더 직관적

두 번째 버전의 단점

• 가독성 저하: truck[0], truck[1]로 의미가 덜 명확
• 실수 가능성: 인덱스 접근 시 순서 헷갈릴 수 있음
• 확장성: 트럭 정보가 더 복잡해지면 관리 어려움

 

코드 상세 분석

초기화 부분

Queue<int[]> bridge = new LinkedList<>(); // [무게, 나가는시간]
int index = 0; // 다음에 출발할 트럭 인덱스
int time = 0; // 현재 시간
int currentWeight = 0; // 다리 위 트럭들의 총 무게

• bridge: 다리 위에 있는 트럭들의 정보 저장
• index: 아직 출발하지 않은 트럭들 중 다음 순서 추적
• currentWeight: 매번 계산하지 않고 변수로 관리해 성능 향상

 

메인 루프

while (index < truck_weights.length || !bridge.isEmpty()) {
    time++;
    // ...
}

 

종료 조건:

• index < truck_weights.length: 아직 출발 안한 트럭이 있거나
• !bridge.isEmpty(): 다리 위에 트럭이 있으면 계속 실행

 

트럭 제거 로직

while (!bridge.isEmpty() && bridge.peek()[1] == time) {
    int[] exitTruck = bridge.poll();
    currentWeight -= exitTruck[0];
}

• bridge.peek()[1] == time: 나가는 시간이 현재 시간과 같은지 확인
• while문 사용: 동시에 여러 트럭이 나갈 수 있음
• currentWeight 업데이트: 나간 트럭 무게만큼 차감

 

트럭 추가 로직

if (index < truck_weights.length) {
    int nextTruckWeight = truck_weights[index];
    if (currentWeight + nextTruckWeight <= weight) {
        bridge.offer(new int[]{nextTruckWeight, time + bridge_length});
        currentWeight += nextTruckWeight;
        index++;
    }
}

• 조건 1: index < truck_weights.length → 대기 중인 트럭이 있는가?
• 조건 2: currentWeight + nextTruckWeight <= weight → 무게 제한 OK?
• 나가는 시간 계산: time + bridge_length → 현재시간 + 다리길이
• index++: 다음 트럭으로 이동
  
  

핵심 포인트

1. 시간 기반 시뮬레이션: 1초씩 시간을 증가시키며 상황 추적
2. 큐(Queue) 활용: 먼저 들어간 트럭이 먼저 나가는 FIFO 구조
3. 미래 시점 계산: 트럭이 언제 나갈지 미리 계산해서 저장
4. 실시간 무게 관리: 다리 위 트럭들의 총 무게를 지속적으로 추적