[프로그래머스] Level 2 다리를 지나는 트럭 (JAVA)

문제

---

1차 풀이 (2021.02.13)

일차선 도로에 트럭들이 순서대로 지난다는 조건에서 Queue를 써야겠다는 생각을 했다. 열심히 구현해봤는데 생각만큼 잘 되지 않아 검색해서 풀었다...!

각 truck마다, truck을 다리에 올릴 때까지 아래 조건문을 반복해서 체크한다.

1. bridge가 비어 있으면 현재 truck을 추가하고 다음 트럭으로 넘어간다.
2. bridge가 bridge_length만큼 꽉 차있으면 마지막 트럭을 bridge에서 제거한다.
3. bridge의 weightSum을 고려하여
   • truck을 추가할 수 있으면 추가하고 다음 트럭으로 넘어간다.
   • truck을 추가할 수 없으면 무게 0의 EMPTY를 추가한다.

코드

import java.util.*;

class Solution {
    
    private static final int EMPTY = 0;

    private int weightSum;
    private Queue<Integer> bridge;
    private int answer;

    public int solution(int bridge_length, int weight, int[] truck_weights) {
        answer = 0;
        weightSum = 0;
        bridge = new LinkedList<>();

        for (int truck : truck_weights) {
            while (true) {
                if (bridge.isEmpty()) {
                    addTruckOnBridge(truck);
                    break;
                }

                if (bridge.size() == bridge_length) {
                    weightSum -= bridge.poll();
                } else if (weightSum + truck <= weight) {
                    addTruckOnBridge(truck);
                    break;
                } else {
                    addTruckOnBridge(EMPTY);
                }
            }
        }

        return answer + bridge_length;
    }

    private void addTruckOnBridge(int truck) {
        bridge.offer(truck);
        weightSum += truck;
        answer++;
    }
}

---

2차 풀이 (2021.08.26)

bridge 큐에다가 truck을 넣는 방식으로 구현했다.

1초(time)에 head 트럭이 도착하고 + tail 트럭이 추가되는 작업이 동시에 이루어지니까, while 루프의 한 바퀴를 1초로 두었다.

head가 bridge 끝에 도착한 경우 제거해준다. 이 때 head의 위치는 bridge.size()와 같다. 1초에 한 대씩 truck이 추가되기 때문에, 추가된 truck 수 만큼 이동한 것이기 때문이다.

또한, 무게초과로 인해 빈 자리에 truck이 추가될 수 없는 경우는 truck 대신 EMPTY를 넣도록 했다. 그래야 head와 나머지 트럭들이 한 칸 전진했다는 것을 알 수 있기 때문이다.

코드

import java.util.*;

class Solution {
    
    private static final int EMPTY = -1;
    
    public int solution(int bridgeLength, int maxWeight, int[] weights) {
        int totalTruckCount = weights.length;
        
        int truck = 0;
        int weightSum = 0;
        
        Queue<Integer> bridge = new LinkedList<>();
        bridge.offer(EMPTY);
        
        int time = 0;
        while (!bridge.isEmpty()) {
            if (truck == totalTruckCount) {
                time += bridgeLength;
                break;
            }
            
            time++;
            
            if (bridge.size() == bridgeLength) {
                int head = bridge.poll();

                if (head != EMPTY) {
                    weightSum -= weights[head];
                }
            }

            if (weightSum + weights[truck] > maxWeight) {
                bridge.offer(EMPTY);
            } else {
                bridge.offer(truck);
                weightSum += weights[truck];
                truck++;
            }
        }
        return time;
    }
}