[JAVA] 스택/큐 "다리를 지나는 트럭"

지금까지 코딩방식과는 느낌이 다르게, 내용 그대로 객체를 코드에 반영하는 느낌이다.

필자는 위 방식이 아니라, 다른 수학적으로 계산을 하려다가 실패하여 다른 코드를 리뷰한다.

 

첫번째, 코드는 Queue에 대기큐와 무브큐를 구현해서, 

1. 무브큐가 비어있을때 if

2. 무브큐의 트럭이 다리를 다 건넌걸 판단하는 if

3. 대기큐에 트럭이 있고, 대기큐의 다음 차례트럭 무게+현재 다리의 무게 < 무게 제한 인 경우 if

import java.util.*;

class Solution {
    class Truck {
        int weight;
        int move;

        public Truck(int weight) {
            this.weight = weight;
            this.move = 1;
        }

        public void moving() {
            move++;
        }
    }

    public int solution(int bridgeLength, int weight, int[] truckWeights) {
        Queue<Truck> waitQ = new LinkedList<>();
        Queue<Truck> moveQ = new LinkedList<>();

        for (int t : truckWeights) {
            waitQ.offer(new Truck(t));
        }

        int answer = 0;
        int curWeight = 0;

        while (!waitQ.isEmpty() || !moveQ.isEmpty()) {
            answer++;

            if (moveQ.isEmpty()) {//무브큐가 비어잇으면
                Truck t = waitQ.poll();//웨이트큐에서
                curWeight += t.weight;//데려와서 다리무게더하고
                moveQ.offer(t);//무브큐로 옮겨
                continue;
            }

            for (Truck t : moveQ) {
                t.moving();//무브큐에 있는것들은 모두 매초마다 움
            }

            //무브큐의 맨 위의 트럭의 이동거리가 다리길이보다 더 큰경우
            if (moveQ.peek().move > bridgeLength) {
                Truck t = moveQ.poll();//빼내고
                curWeight -= t.weight;//그만큼 다리무게에서 뺌
            }

            //추가작업!
            //대기중인게 있고, 다음차례트럭과 현재트럭 무게 합이 제한보다 작을때
            if (!waitQ.isEmpty() && curWeight + waitQ.peek().weight <= weight) {
                Truck t = waitQ.poll();//웨이트큐에서 빼서
                curWeight += t.weight;
                moveQ.offer(t);//무브큐로 옮긴다.
            }
        }

        return answer;
    }
}

 

다음은 해시 맵을 이용한 코드의 리뷰이다.

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
            Stack<Integer> truckStack = new Stack<>();
            Map<Integer, Integer> bridgeMap = new HashMap<>();

            for (int i = truck_weights.length-1; i >= 0; i--)
                truckStack.push(truck_weights[i]);

            int answer = 0;
            int sum = 0;
            while(true) {
                answer++;

                if (bridgeMap.containsKey(answer))
                    bridgeMap.remove(answer);
                    
				//다리위의 적체량 합 구하기
                sum = bridgeMap.values().stream().mapToInt(Number::intValue).sum();

                if (!truckStack.isEmpty())
                    if (sum + truckStack.peek() <= weight)//다음트럭+현재 적체량 값 비교
                        bridgeMap.put(answer + bridge_length, truckStack.pop());

                if (bridgeMap.isEmpty() && truckStack.isEmpty())
                    break;


            }
            return answer;
    }
}

위의 방식은 필자가 구현하려고 했던 방향과 유사하다.

여기서 포인트는

bridgeMap.put(answer + bridge_length, truckStack.pop());answer + bridge_length는 트럭을 다리에 입고시킬때, 미리 탈출시간을 계산해놓는 것이다.

 

그리고 시간이 경과해서 answer값이 해당 Key값에 도달하면 = if(bridgeMap.containsKey(answer))

해당 Key값을 가진(도착한)트럭을 다리에서 삭제시킨다 = bridgeMap.remove(answer);