[프로그래머스] 다리를 지나는 트럭 - Java

문제 설명

 

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

 

접근 방법

해당 문제는 큐(Queue) 자료구조를 이용하여 해결할 수 있었습니다. 문제에 따르면 트럭의 상태는 "대기 트럭"과 "다리를 건너는 트럭" 그리고 "다리를 지난 트럭"으로 나뉩니다. 이때 각각의 트럭의 상태들을 관리할 큐 자료구조를 만들어 줍니다.("다리를 지난 트럭"에 대한 큐 자료구조는 별도로 만들 필요없습니다.)

 

이후 다리를 건널 수 있는 조건(무게와 트럭 대수)을 충족 하는 경우 "대기 트럭을 담은 큐"에서 트럭을 빼내어 "다리를 건너는 트럭을 담은 큐"에 넣습니다. 이때 다리를 건너는 트럭이 발생함에 따라 무게와 트럭 대수를 업데이트(update) 해줍니다. 또한 다리를 건너는 트럭들이 다리를 완전히 건넌다면 이들을 다리를 건너는 트럭을 담은 큐에서 빼내고 마찬가지로 무게와 트럭 대수를 업데이트(update) 해줍니다.

 

 

전체 소스 코드

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

class Solution {

    static class Truck {

        int weight;
        int movingTime;

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

        public void plus() {
            movingTime++;
        }
    }

    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> waitingTrucks = new LinkedList<>();
        for (int truckWeight : truck_weights) {
            waitingTrucks.add(truckWeight);
        }

        int time = 1, presentWeight = waitingTrucks.poll(), presentCountOfTrucks = 1;

        Queue<Truck> passingTrucks = new LinkedList<>();
        Truck truck = new Truck(presentWeight, 0);
        passingTrucks.add(truck);

        while (!waitingTrucks.isEmpty()) {
            passingTrucks.forEach(Truck::plus);

            if (passingTrucks.peek().movingTime == bridge_length) {
                presentWeight -= passingTrucks.poll().weight;
                presentCountOfTrucks--;
            }

            time++;

            if (presentWeight + waitingTrucks.peek() <= weight
                && presentCountOfTrucks <= bridge_length) {

                int w = waitingTrucks.poll();
                passingTrucks.add(new Truck(w, 0));
                presentWeight += w;
                presentCountOfTrucks++;
            }
        }

        return time + bridge_length;
    }
}

 

 

참고자료

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