프로그래머스 스택/큐 LV2 - 다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간                다리를 지난 트럭                              다리를 건너는 트럭             대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

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

입출력 예

bridge_length  weight        truck_weights                                                                                 return

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

출처

※ 공지 - 2020년 4월 06일 테스트케이스가 추가되었습니다.

 

---

import java.util.*;
class Solution {
        Queue<truck> rail = new LinkedList<>();
        Queue<Integer> wait = new LinkedList<>();
        Queue<Integer> finish = new LinkedList<>();
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int len = truck_weights.length;
        for(int i=0; i<truck_weights.length; i++) wait.add(truck_weights[i]);
        
        while(true){
            if(getsum()<weight&&rail.size()<=bridge_length&&wait.size()>0){
                int temp = wait.poll();
                if(getsum()+temp>weight){
                    addfirst(temp);
                    answer++;
                    if(check(answer,bridge_length)){
                        rail.poll();
                    }
                    continue;
                }
                if(rail.size()+1>bridge_length){
                    addfirst(temp);
                    answer++;
                    if(check(answer,bridge_length)){
                        rail.poll();
                    }
                    continue;
                }
                rail.add(new truck(temp, answer+1));
                answer++;
                if(check(answer,bridge_length)){
                    rail.poll();
                }
            }
            else answer++;
            if(check(answer,bridge_length)){
                    rail.poll();
            }

            if(finish.size()==truck_weights.length) break;
        }
        
        return answer+1;
    }
    int getsum(){
        if(rail.size()==0) return 0;
        int sum = 0;
        for(int i=0; i<rail.size(); i++){
            truck temp = rail.poll();
            sum+=temp.num;
            rail.add(temp);
        }
        return sum;
    }
    void addfirst(int a){
        int size = wait.size();
        wait.add(a);
        for(int i=0; i<size; i++){
             int temp = wait.poll();
             wait.add(temp);
        }
    }

    boolean check(int time, int length){
        int size = rail.size(); 
         truck temp = rail.peek();
         if(time == temp.time+length-1){
             finish.add(temp.num);
             return true;
         }
         else{
             return false;
         }
        
    }
}
class truck{
    int num;
    int time;
    truck(int n, int t){
        this.num = n;
        this.time = t;
    }
}

다리 위에 트럭을 넣을 때 해당 트럭이 들어간 시간을 저장하는 방법이 필요해서 truck이라는 클래스를 만들어서 그 객체 안에 트럭의 무게와 시간을 같이 넣었다. 

그 후에 시간의 증가가 있을 때마다 현재 시간과 (다리 위에 있는 첫번째 객체의 입차 시간 + 다리의 길이 -1)이 일치하는지 확인하고 일치하면 해당 트럭을 다리를 건넌 것으로 판단하고 마지막 QUEUE로 옮겼다.

그리고 while문을 탈출하고, 모든 트럭이 다리를 건넌 시간 1초를 더 해서 return 하였다.