[JAVA] 프로그래머스 : 다리를 지나는 트럭 (코딩테스트 고득점 kit > 스택/큐)

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

코딩테스트 연습 - 다리를 지나는 트럭

첫 번째 풀이

해결 방안

큐를 제대로 이해하고 있으면 풀 수 있는 문제였음

큐와 문제의 주어진 조건을 이용해서 푸는 문제.
각 트럭이 다리 길이 갔을 때 나가는 걸 체크하기 위해 enterTime을 활용

코드

import java.util.*;
// 다리를 지나는 트럭
// 모든 트럭이 다리를 건너는데 걸리는 시간

class Solution {
    static class Truck{
        int enterTime;
        int weight;
        
        Truck(int enterTime, int weight){
            this.enterTime = enterTime;
            this.weight = weight;
        }
    }
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        int totalWeightOnBridge = 0;
        
        // 대기 트럭
        Queue<Truck> waiting_truck = new LinkedList<Truck>();
        // 다리를 건너는 트럭
        Queue<Truck> crossing_truck = new LinkedList<Truck>();
        
        // 대기 트럭 입력
        for(int i=0; i<truck_weights.length; i++){
            waiting_truck.offer(new Truck(0, truck_weights[i]));
        }
        
        //매 초 일어나는 동작 정의(대기 트럭과 다리를 건너는 트럭이 둘다 비어있지 않으면 실행)
        while(!(waiting_truck.isEmpty() && crossing_truck.isEmpty())){
            time ++;
            
            // 다리를 건너는 트럭이 있을 때
            if(!crossing_truck.isEmpty()){
                // 1. 다리를 나가야하는 트럭이 있는지 확인
                // 1.1. 해당 트럭의 (현재 시간-들어간 시간) >= bridege_length 이면 나감
                if((time - crossing_truck.peek().enterTime) >= bridge_length){
                    totalWeightOnBridge -= crossing_truck.peek().weight;
                    crossing_truck.poll();
                }
            }
            
            if(!waiting_truck.isEmpty()){
            	// 2. 대기 트럭이 다리를 올라가도 되는지 확인
            	if(totalWeightOnBridge + waiting_truck.peek().weight <= weight){
            		totalWeightOnBridge += waiting_truck.peek().weight;
            		
            		crossing_truck.offer(new Truck(time, waiting_truck.peek().weight));
            		waiting_truck.poll();
            	}
            }
        }
        
        return time;
    }
}

 

두 번째 풀이

해결 방안

첫 번째 풀이와 비슷하게 해결

코드

import java.util.*;

// 다리를 지나는 트럭
// 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려함
// 모든 트럭이 다리를 건너려면 최소 몇초가 걸리는지 알아내야함 (트럭은 1초에 1만큼 움직임)
class Solution {
    
    class Truck{
        public int weight; // 해당 트럭 무게
        public int enterTime; // 다리에 진입한 시간
        
        Truck(int weight, int enterTime){
            this.weight = weight;
            this.enterTime = enterTime;
        }
    }
    
    // bridge_length: 다리 길이, weight: 다리가 버틸 수 있는 무게
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        
        // 대기 트럭
        Queue<Truck> waitingQ = new LinkedList<>();
        // 다리를 건너는 트럭
        Queue<Truck> crossingQ = new LinkedList<>();
        
        // 대기 트럭에 트럭 넣어주기
        Truck truck;
        for(int i=0; i<truck_weights.length; i++){
            truck = new Truck(truck_weights[i], -1);
            waitingQ.offer(truck);
        }
        
        // 다리를 지난 트럭은 대기 트럭과 다리를 건너는 트럭의 Queue가 다 empty인 경우임(while의 조건)
        int totalWeight = 0; // 다리에 올라와있는 트럭들의 무게
        int truck_weight;
        int truck_enterTime;
        Truck waitingTruck;
        Truck crossingTruck;
        while(!waitingQ.isEmpty() || !crossingQ.isEmpty()){
            // 시간 증가에 따른 트럭 움직임
            time ++;
            
            // 다리를 건너는 트럭 enterTime 확인해서 다리를 다 지났는지 확인
            // 꼭 먼저 확인해줘야 함 (다리를 건너던 트럭이 지나가서 대기 트럭이 올라올 수 있으므로)
            if(!crossingQ.isEmpty()){
                crossingTruck = crossingQ.peek();
                truck_enterTime = crossingTruck.enterTime;
                truck_weight = crossingTruck.weight;
                
                if(time - truck_enterTime >= bridge_length){
                    crossingQ.poll();
                    totalWeight -= truck_weight;
                }
            }
            
            // 대기 트럭이 다리에 올라올 수 있는지 무게 확인해서 견딜 수 있는 무게이면 다리에 올리기
            if(!waitingQ.isEmpty()){
                waitingTruck = waitingQ.peek();
                truck_weight = waitingTruck.weight;
                truck_enterTime = time;
                
                if(truck_weight + totalWeight <= weight){
                    crossingTruck = new Truck(truck_weight, truck_enterTime);
                    crossingQ.offer(crossingTruck);
                    
                    waitingQ.poll();
                    totalWeight += truck_weight;
                }
            }
            
        }
        
        // while 조건을 다 빠져나오면 모든 트럭이 다리를 지나간거임
        return time;
    }
}