다리를 지나가는 트럭 (큐)

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

프로그래머스

 

 

 

문제 풀이

• 트럭이 순서대로 움직이므로 큐를 사용!
• 트럭이 1초부터 올라간다는 것을 주의

 

 

작성한 코드 (정답)

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        
        int time = 1;

        Queue<Truck> bridgeQue = new LinkedList<>(); // 다리 위 트럭 큐
        Queue<Truck> trucks = new LinkedList<>(); // 대기 중인 트럭 큐

        // 트럭 배열 큐로 변환
        for (int w : truck_weights) {
            trucks.add(new Truck(0,w));
        }

        while (true) {

            //// 다리 위 트럭 내리기
            if (!bridgeQue.isEmpty() && time - bridgeQue.peek().getOnTime() >= bridge_length) {
                bridgeQue.remove();
            }

            //// 다리 위에 트럭 없고, 올릴 트럭 없으면 종료
            if (trucks.isEmpty() && bridgeQue.isEmpty()) break;

            // 다리 꽉 차면 새 트럭 못 올림
            if (bridgeQue.size() == bridge_length || trucks.isEmpty()) {
                time++;
                continue;
            }
            
            // 새 트럭 다리에 올리기
            int bridgeWeight = bridgeQue.stream().mapToInt(Truck::getWeight).sum();
            Truck truck = trucks.peek();
            if (weight >= bridgeWeight + truck.getWeight()) {
                truck.setOnTime(time);
                bridgeQue.add(truck);
                trucks.remove();
            }

            time++;
        }

        return time;
    }

     public static class Truck {
        private int onTime = 0;
        private int weight = 0;

        public Truck(int onTime, int weight) {
            this.onTime = onTime;
            this.weight = weight;
        }

        public int getOnTime() {
            return onTime;
        }

        public void setOnTime(int onTime) {
            this.onTime = onTime;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }
}

 

 

후기

•  최소 시간이라는 단어를 보고 다리에 올리는 트럭의 순서를 조정하면서 가장 빨리 모든 트럭이 지나가는 시간을 찾는 문제인줄 알고 그리디 알고리즘을 적용했다가 시간을 많이 날려먹었다... 
•  큐의 사용법에 대해서 다시 한 번 공부하는 계기가 되었다.