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

🔗 문제 링크

[프로그래머스] 다리를 지나는 트럭

코딩테스트 연습 - 다리를 지나는 트럭

 

📝 풀이 과정

트럭은 정해진 순서로 진입하고 진입한 순서대로 다리에서 빠져나오기 때문에 Queue를 사용하기로 했다.

 

if (!queue.isEmpty() && time == queue.peek()[1]) {
  int[] truck = queue.poll();
  weight += truck[0];
}

Queue에 int배열로 {진입한 트럭의 무게, 도달시간} 순으로 넣고, time을 반복할 때마다 하나씩 증가시키며 도달시간과 일치하게 되면 Queue에서 제거해 주고 weigth을 다시 더해 추가로 트럭이 진입할 수 있게 하였다.

 

 

if (weight >= truck_weights[idx]) {
  queue.add(new int[]{truck_weights[idx], time + bridge_length});
  weight -= truck_weights[idx++];
}

만약 남은 무게가 현재 가리키고 있는 트럭의 무게보다 작다면 트럭을 Queue에 넣어주고 idx를 증가하고, weight값을 무게만큼 감소시켰다.

 

 

마지막까지 트럭이 진입해 반복문이 종료된다면 마지막 트럭이 진입한 시간이 time이 되고, 마지막 트럭이 다리에서 나오는 시간은 time + bridge_length가 되기 때문에 이를 반환해준다.

 

⏱ 시간 복잡도

다리의 최고 길이는 10,000이고, 트럭은 최대 10,000대가 존재하기 때문에 최대 $10^8$번 반복하게 된다.

 

💻 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<int[]> queue = new LinkedList<>();
        int time = 0, idx = 0;

        while (idx < truck_weights.length) {
            if (!queue.isEmpty() && time == queue.peek()[1]) {
                int[] truck = queue.poll();
                weight += truck[0];
            }

            if (weight >= truck_weights[idx]) {
                queue.add(new int[]{truck_weights[idx], time + bridge_length});
                weight -= truck_weights[idx++];
            }

            time++;
        }

        return time + bridge_length;
    }
}