[프로그래머스] 코테연습 - 다리를 지나는 트럭 (lv.2)

- 내 방법 풀이

• 전형적인 큐를 사용하는 문제였다. 고속도로 요금소와 마찬가지로 FIFO 구조의 자료였기 때문에 처음에 큐에 모든 트럭을 넣어놓고 다리 길이와 같은 길이의 배열을 생성하여 트럭을 올리는 방법을 생각했다. 그러나 코드의 효율성이 떨어져서, 접근 방법을 다시 고민하기 위해 구글링을 했다.
• 구글링 후, 다리 = 큐 로  방향을 설정하고 코드를 짰다. 큐의 합산이 제한 하중을 넘지 않을 때 트럭을 올리며 시간을 증가시킨다. 제한 하중을 넘었다면 0을 추가하여 올린 트럭을 이동시킨다. 큐의 길이가 다리 길이와 같아졌을 때, 트럭을 다리위에서 내린다.

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int weightSum = 0;
        Queue<Integer> queue = new LinkedList<>();
    
        for (int i : truck_weights) {
            while (true) {
                if (queue.isEmpty()) {
                    queue.add(i);
                    weightSum += i;
                    answer++;
                    break;
                }
                else if (queue.size() == bridge_length) weightSum -= queue.poll();
                else {
                    if (weightSum + i <= weight) {
                        queue.add(i);
                        weightSum += i;
                        answer++;
                        break;
                    } else {
                        queue.add(0);
                        answer++;
                    }
                }
            }
        }
        answer +=bridge_length;
        return answer;
    }
}

- 다른 사람 방법 풀이

• 이 사람은 Queue를 2개 생성하여 하나는 대기중, 하나는 다리위의 트럭을 넣는 용도로 사용하였다. 두 개의 큐가 모두 빌 때까지 while문을 실행시켰다.
• 어떤 동작이 일어나든 시간을 소모하도록 조건을 짜서 while문 맨 처음에 answer++ 시킨 것이 흥미로웠다.
• moving큐 위에 있는 트럭은 시간의 흐름에 따라 이동하며, 다리를 벗어났다면 제한 하중의 합에서 제외시킨다.
• wati큐에 있는 트럭을 올려도 제한 하중을 초과하지 않는다면 트럭을 moving큐에 추가한다.

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;
    }
}