[Java] 프로그래머스 Lv.2 > 다리를 지나는 트럭

https://programmers.co.kr/learn/courses/30/lessons/42583?language=java 

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

 

풀이

스택/큐 문제였다. 트럭이 다리를 건너는 순서대로 빠져나와야하기 때문에 큐를 사용했다.

다리를 의미하는 queue를 만들어주고, 조건에 맞게 트럭을 큐에서 넣고 빼준다.

• 다리 위 트럭이 없는 경우(맨 처음)에는 트럭을 queue에 넣어준다.
• 다리 위에 트럭이 다 찬 경우(q.size()== bridge_length) 에는 queue에서 트럭을 빼준다.
• 다리 위에 트럭이 이미 있는 경우, 현재 대기중인 트럭 포함 무게가 weight 이하일 때만 트럭을 queue에 넣어준다.
• 트럭 위치 이동을 위해, 트럭을 넣지 않을 때는 queue에 0을 넣어줘 위치이동을 표현한다.
• 다리 위에서 트럭이 1칸씩 움직일 때마다 시간이 흐르기 때문에, queue.offer() 해줄 때 time++을 해준다.

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0; // 걸린 시간 -> qb에 offer해줄때 증가시킴
        int sum = 0; // 다리 위 트럭 무게
        Queue<Integer> q = new LinkedList<>(); // 다리 위 트럭
        
        for(int truck : truck_weights){
            while(true){
                if(q.isEmpty()){ // 다리 위 트럭 없는 경우
                    q.offer(truck);
                    sum += truck;
                    time++;
                    break;
                }else if(q.size() == bridge_length){ // 다리위에 트럭 다 찬경우
                    sum -= q.poll(); // 트럭 다리에서 빼줌
                }else{
                    // 현재 트럭 포함 sum 무게가 weight이하일 때 다리 위에 올려줌
                    if(sum + truck<=weight){
                        q.offer(truck);
                        sum +=truck;
                        time++;       
                        break;                     
                    }else{
                        q.offer(0); // 트럭 위치이동을 위한 0 넣기
                        time++;
                    }
                }
            } 
        }
        
        return time+bridge_length; // 마지막트럭이 다리길이만큼 지나가는시간 추가
    }
}

 

Truck 클래스 사용

사실 처음에 풀려고 했던 방식인데, Truck 클래스 없이 두 Queue만 만들어서 하다보니, 다리 위 트럭이 여러개 일 때 각 트럭마다 다리를 다 지나가는 타이밍을 잡아 큐에서 빼주는 방법을 알지못해 사용하지 못했다.

이후, Truck 클래스를 만들어 트럭에게 position을 주면 된다는 것을 알게되었다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static class Truck{
        int position;
        int weight;
        
        public Truck(int weight){
            this.weight = weight;
            this.position=0;
        }
    }
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0; // 걸린 시간
        int sum = 0; // 다리 위 트럭 무게
        Queue<Truck> qt = new LinkedList<>(); // 대기 트럭
        for(int truck : truck_weights)
            qt.offer(new Truck(truck));
        
        Queue<Truck> qb = new LinkedList<>(); // 다리 위 트럭
        qb.offer(qt.poll()); // 첫번째 대기트럭 올려줌
        sum += qb.peek().weight; // 무게더함
        
        while(!qb.isEmpty()){ // 다리건너는 트럭이 비어있으면 멈춤
            time++;
            // 다리 위 트럭 이동
            for(Truck truck : qb){
                truck.position++;
            }
            
            // 다리 다 건너면 트럭 빼줌
            if(qb.peek().position > bridge_length){
                sum-= qb.poll().weight;
            }
            
            // 다리에 자리 있을 때, 무게가 넘지않으면 새로운 트럭 넣어줌
            if(qt.isEmpty()==false && (sum + qt.peek().weight) <= weight){
                sum += qt.peek().weight;
                qt.peek().position++;
                qb.offer(qt.poll());
            }
        }
        
        return time;
        
    }

}