[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);