[코딩테스트] Java 다리를 지나는 트럭

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

다리를 큐로 표현해 각 트럭의 상태를 관리하며, 트럭이 다리를 건너는 동안의 시간과 다리의 무게 제한을 고려해 순차적으로 트럭을 다리에 올리고 내립니다. 반복문은 트럭이 모두 다리를 건널 때까지 계속됩니다.

 

 

소스코드

import java.util.*;

class Solution {
    static class Truck {
        int weight, position;

        public Truck(int weight) {
            this.weight = weight;
            this.position = 0;
        }

        public Truck(int weight, int position) {
            this.weight = weight;
            this.position = position;
        }
    }
    
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0; // 경과 시간
        int bridgeWeight = 0; // 현재 다리 위의 트럭 총 무게
        Queue<Truck> bridge = new LinkedList<>(); // 다리 위의 트럭 큐
        int idx = 0; // 대기 트럭 인덱스

        while (idx < truck_weights.length || !bridge.isEmpty()) {
            time++;

            if (!bridge.isEmpty()) {
                Truck frontTruck = bridge.peek(); // 맨 앞의 트럭
                if (time - frontTruck.position >= bridge_length) { // 다리를 다 건넜을 경우
                    bridgeWeight -= frontTruck.weight; // 다리 무게에서 제외
                    bridge.poll(); // 트럭 다리에서 내림
                }
            }

            if (idx < truck_weights.length) {
                if (bridgeWeight + truck_weights[idx] <= weight && bridge.size() < bridge_length) {
                    bridge.add(new Truck(truck_weights[idx], time)); // 트럭 다리에 올림
                    bridgeWeight += truck_weights[idx]; // 현재 다리 무게 갱신
                    idx++; // 대기 트럭 인덱스 증가
                }
            }
        }
        return time;
    }
}

코드 설명

 

• Truck 클래스
  • weight: 트럭의 무게.
  • position: 트럭이 다리를 건너기 시작한 시점(시간).
• 변수 초기화:
  • time: 전체 시뮬레이션의 경과 시간을 나타냅니다.
  • bridgeWeight: 현재 다리 위에 있는 트럭들의 총 무게입니다.
  • bridge: 현재 다리를 건너고 있는 트럭들을 저장하는 큐입니다.
  • idx: 대기 중인 트럭을 가리키는 인덱스입니다.
• 메인 로직:
  • 시간 증가: 매 반복마다 time이 증가합니다. 이는 시뮬레이션의 한 단계를 의미합니다.
  • 트럭 이동:
    • bridge 큐에서 맨 앞에 있는 트럭(frontTruck)의 위치를 확인합니다.
    • time - frontTruck.position이 bridge_length보다 크거나 같다면, 트럭은 다리를 건넜으므로 bridge.poll()로 큐에서 제거하고, bridgeWeight에서 트럭의 무게를 뺍니다.
  • 새 트럭 추가:
    • 아직 다리를 건너지 않은 트럭이 있을 경우(idx < truck_weights.length), 현재 다리의 무게(bridgeWeight + truck_weights[idx])가 제한을 초과하지 않고 다리 길이 조건을 만족하면 새 트럭을 bridge에 추가합니다.
    • 새 트럭이 다리에 추가되면 bridgeWeight를 업데이트하고 idx를 증가시켜 다음 트럭을 가리킵니다.
• 종료 조건:
  • 대기 중인 트럭이 더 이상 없고(idx >= truck_weights.length), bridge에 남아 있는 트럭도 없을 때 시뮬레이션이 종료됩니다.
• 결과 반환:
  • 최종적으로 경과된 time을 반환합니다. 이는 모든 트럭이 다리를 건너기까지 걸린 총 시간입니다.