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

문제

---

 

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

문제 분석

---

[제한 조건]

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

다리의 길이와 다리가 견딜 수 있는 무게 그리고 트럭들의 무게가 주어졌을 때 모든 트럭이 다리를 지나가는데 필요한 시간을 구하는 문제이다.

 

다리에는 들어 온 순서대로 나가기 때문에 큐 자료구조를 활용할 수 있을 것 같다.

 

문제 접근

---

다리에는 들어 온 순서대로 나가고 대기 중인 트럭 역시 앞에서 부터 차례대로 나가기 때문에 큐 자료구조를 활용하면 풀 수 있다.

 

제한 조건을 확인해 보자

최악의 경우는 다리 길이가 10,000 이고 10,000 개의 트럭이 다리를 지나면서 다리에 하나의 트럭만 올라가는 경우이다.

이 경우에도 10,000 X 10,000 = 10^8 이다. 

시간을 1씩 증가시켜준다면 운이 좋다면 아슬아슬하게 통과 가능할 거 같다.

 

시도해 보고 실패한다면 조금 더 최적화 시켜보자.

-> 성공했음

 

다리 위에 올라가 있는 트럭을 나타내는 큐 와 대기 중인 트럭을 나타내는 큐 2개를 만들어 사용하였다.
(다리 위를 나타내는 큐는 [트럭 무게, 거리] 형태로 큐에 값을 넣었다.)

아래 과정을 두 큐가 모두 빌 때 까지 반복한다.

다리 위의 트럭들의 이동 거리 ++
만약 다리를 빠져 나오는 트럭이 있다면 큐에서 빼주고, 현재 트럭들의 무게도 업데이트 한다.

대기 큐의 제일 앞에 있는 트럭의 무게 + 현재 트럭들의 무게가 다리가 견딜 수 있는 무게보다 작다면
대기 큐에서 하나 빼서 다리 큐에 넣고 현재 트럭들의 무게도 업데이트 한다.

시간 ++

 

코드

---

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        int curWeight = 0;
        Queue<int[]> bridgeTrucks = new LinkedList<>();
        Queue<Integer> readyTrucks = new LinkedList<>();
        
        for(int truck : truck_weights){
            readyTrucks.offer(truck);
        }
        
        int nextTruck = readyTrucks.poll();
        curWeight += nextTruck;
        
        bridgeTrucks.offer(new int[]{nextTruck, 1});
        time++;
        
        
        while(!bridgeTrucks.isEmpty() || !readyTrucks.isEmpty()){
            move(bridgeTrucks);
            if(!bridgeTrucks.isEmpty() && bridgeTrucks.peek()[1] > bridge_length){
                int[] removeTruck = bridgeTrucks.poll();
                curWeight -= removeTruck[0];
            }
            
            if(!readyTrucks.isEmpty() && readyTrucks.peek() + curWeight <= weight){
                nextTruck = readyTrucks.poll();
                curWeight += nextTruck;
        
                bridgeTrucks.offer(new int[]{nextTruck, 1});
            }
            time++;
        }
        return time;
    }
    public void move(Queue<int[]> bridgeTrucks){
        for(int[] truck : bridgeTrucks){
            truck[1]++;
        }
    }
}