문제 출처

코딩테스트 연습 > 스택/큐 > 다리를 지나는 트럭
https://school.programmers.co.kr/learn/courses/30/lessons/42583

문제 설명

다리에 올라갈 수 있는 트럭 수 bridge_length, 다리 견디는 무게 weight, 트럭 별 무게 trucks_weight 이라 할 때, 이 트럭들이 다리를 건너는 총 시간을 구하는 문제이다. 다리에 트럭이 올라갈 때, 다리에 올라간 트럭의 무게는 weight를 넘기면 안되므로, weight를 넘기기 전에 앞서간 트럭이 먼저 지나가야한다.

% 트럭이 다리에 올라가는 시간은 1초이고, 트럭이 다리를 다 건너기 위해서는 bridge_length가 지나야한다.

접근 방법

가장 단순하게 다리 자체를 "큐(Queue)"라고 생각하면 편하다. 큐에 bridge_length 만큼 0(여백)을 삽입한다. 그리고, 트럭이 다리를 다 지날 때까지{i(index)가 truck_weight.length 가 되거나, sum <= 0 이 될 때까지} sum에서 현재 트럭 무게를 빼준 뒤의 sum과 다음 트럭 무게를 더했을 때, weight보다 적으면 큐에 다음 트럭을 add 해주면 된다. 만약 weight보다 크다면 큐에 공백(0)을 삽입하면 된다. 해당 과정에서 while문이 돌 때마다 answer을 증가시킨다.

% 설명이 조금 지저분하지만 코드로 보면 이해가 될 것이다.

import java.util.*;

class Solution {
   public int solution(int bridge_length, int weight, int[] truck_weights) {
       int answer = 0;
       int sum = 0;
       Queue<Integer> q = new LinkedList<>();
       int i =0;
       
       for (i =0; i<bridge_length;i++){
           q.add(0);
       }
       i = 0;
       
       while(i < truck_weights.length || sum > 0){
           sum -= q.remove();
           if(i<truck_weights.length && sum + truck_weights[i] <= weight){
               q.add(truck_weights[i]);
               sum+=truck_weights[i];
               i++;
           } else{
               q.add(0);
           }
           answer++;
       }
       return answer;
   }
}

Review
앞 선 코드에서는 sum의 값이 남아있으면 계속 while문을 돌게하여 sum이 0이 될 때까지 반복 시켰지만, Reivew에서는 인덱스 i가 truck_weights.length가 되면 bridge_length 만큼 더하여 answer을 return하게 했다.
앞 선 코드가 조금 더 깔끔하게 돌아가지만, 수행하는 횟수는 Review 코드가 더 짧을 것이다.

import java.util.*;

class Solution {
   public int solution(int bridge_length, int weight, int[] truck_weights) {
       Queue<Integer> q = new LinkedList<>();
       int sum = 0;
       int i = 0;
       int answer = 0;
       
       for(i = 0; i<bridge_length; i++){
           q.add(0);
       }
       
       i = 0;
       
       while(!q.isEmpty() && i <truck_weights.length){
           sum -= q.poll();
           if(sum + truck_weights[i] > weight){
               q.add(0);
           }else{
               q.add(truck_weights[i]);
               sum += truck_weights[i++];
           }
           answer++;
           if(i == truck_weights.length) answer+= bridge_length;
       }
       return answer;
}
}

알게된 점

이 문제도 잘 풀지 못했다. 처음에는 큐가 없어도 풀 수 있지 않나? 라는 생각으로 sum과 weight를 비교하여 계산하려했으나 복잡해져서 풀지 못 했다.
다른 사람들이 푼 것과 GPT를 통해 "다리 자체를 큐로 생각하라"를 알 수 있었다. 해당 방식을 이해만 하면 정말 쉽게 풀 수 있는 문제 인 것 같다.

문제푼 흔적