프로그래머스 - 다리를 지나는 트럭 (JAVA)

프로그래머스 다리를 지나는 트럭 풀이 과정
과거의 나 자신과 현재의 나, 둘 다 정답을 냈다.
신기하게도 접근법이 완전히 달랐다.
총 2번의 제출

1트 (정답) → 매초 트럭 위치를 직접 갱신하는 시간 기반 시뮬레이션
2트 (정답, 과거의 나) → 빈 슬롯을 0으로 채우는 포화 상태 기반 시뮬레이션

---

1트 (정답)

→ 매초 다리 위 트럭의 위치를 직접 갱신하는 방식으로 접근했다.
→ 큐에 [무게, 현재 위치]를 함께 저장하면, 위치가 bridge_length를 넘었을 때 자연스럽게 제거할 수 있겠다고 생각했다.
→ 큐가 완전히 비면 모든 트럭이 다리를 건넌 것이니 그걸 종료 조건으로 삼았다.

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Deque<int[]> bridge = new LinkedList<>(); // 다리

        int curWeight = 0;
        int idx = 0;
        int time = 0;

        while(true) {
            time++;
            // 트럭별 다리 위치 갱신
            if(!bridge.isEmpty()) {
                int size = bridge.size();
                for(int i=0; i<size; i++) {
                    int[] cur = bridge.poll();

                    // 다리 다 건넜을 경우
                    if(cur[1] + 1 > bridge_length) {
                        curWeight -= cur[0];
                        continue;
                    }

                    bridge.offer(new int[] {cur[0], ++cur[1]});
                }
            }

            // 다리 무게 검사 후 진행
            if(idx < truck_weights.length && curWeight + truck_weights[idx] <= weight) {
                bridge.offer(new int[] {truck_weights[idx], 1});
                curWeight += truck_weights[idx++];
            }

            if(bridge.isEmpty()) break;
        }

        return time;
    }
}

위 풀이의 결과

• 정답은 맞지만, 매초 큐 전체를 순회해서 위치를 갱신하는 게 조금 무겁다.
• 그래도 트럭이 어디 있는지 눈에 보이는 구조라 디버깅하기 편했다.
• [무게, 위치] 쌍을 직접 관리하다 보니 코드가 다소 길어졌다.

---

2트 (정답, 과거의 나)

→ 다리를 고정된 크기의 큐로 모델링했다. 트럭이 없는 빈 자리엔 0을 밀어 넣었다.
→ 큐의 size가 bridge_length에 꽉 차면, 맨 앞 트럭을 무조건 꺼내는 방식이다.
→ 반복문은 마지막 트럭이 큐에 들어가는 순간 탈출한다.
→ 그 시점에 마지막 트럭은 다리 첫 번째 칸에 막 올라선 상태이므로, answer += bridge_length로 나머지 시간을 보정해줬다.

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Deque<Integer> dq = new LinkedList<>();
        dq.offer(truck_weights[0]);
        int cur_weight = truck_weights[0];
        int answer = 1;
        int idx = 1;

        // 현재 인덱스가 트럭배열 길이보다 작을 경우 반복
        while(idx < truck_weights.length) {
            int size = dq.size();

            // 다리 포화상태 x
            if(size < bridge_length) {
                if(cur_weight + truck_weights[idx] <= weight) {
                    dq.offer(truck_weights[idx]);
                    cur_weight += truck_weights[idx++];
                }
                else dq.offer(0);

                answer++;
            }

            // 다리 포화상태 o, 트럭 하나 무조건 나와야함
            else cur_weight -= dq.poll();
        }

        // 마지막 트럭이 다리 첫번째 위치에 있는 상태로 반복문 탈출
        // 다리 위 차가 다 건너려면, 마지막 차량이 빠져나와야 함
        // 즉, 소요시간 = 반복문 탈출 시간 + 마지막 차량 다리 건너는 시간(다리 길이)
        answer += bridge_length;

        return answer;
    }
}

위 풀이의 결과

• 코드가 훨씬 짧고 깔끔하다. 과거의 내가 더 잘 짠 것 같아서 조금 억울하다.
• 포화 상태 분기(else)에서 answer++가 없다는 점에 주의해야 한다.
• 저 else는 시간이 흐르는 게 아니라 앞 트럭을 빼는 전처리 단계이기 때문이다.
• 반복문 탈출 후 +bridge_length 보정을 빼먹으면 바로 오답이 된다. 과거의 나는 이걸 어떻게 알았을까.

---

같은 문제를 두 번 풀었는데 접근법이 완전히 달랐다. 1트는 위치를 직접 추적하는 방식이라 코드가 길지만 흐름이 직관적이고, 2트(과거의 나)는 빈 슬롯을 0으로 채워 넣는 방식으로 훨씬 간결하다.
다만 2트 방식은 반복문 탈출 시점과 +bridge_length 보정 두 가지를 정확히 이해하고 짜야 한다. 이 두 가지 중 하나라도 놓치면 경계 조건에서 1~2 차이로 오답이 난다.
앞으로 시뮬레이션 문제에서 "굳이 위치를 추적할 필요가 있나, 슬롯 개념으로 추상화할 수 있지 않나" 를 먼저 생각해보는 습관을 들여야겠다.