[프로그래머스 / 스택&큐] 다리를 지나는 트럭 (java)

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 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_lengthweighttruck_weightsreturn

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

 

[문제 접근]
큐를 이용한다.
현재 다리 위의 무게 onWeight와 다음 트럭의 무게를 더한 nextWeight이 weight를 넘지 않으면
트럭을 다리 위로 올린다. (큐에 추가시킨다.) 그리고 time을 증가시키고, onWeight에 트럭의 무게를 추가시킨다. 트럭의 인덱스를 증가시킨다.
무게를 넘는다면 트럭의 인덱스를 증가시키고 (다리 위에서의 위치를 한 칸 옮기고), 타임을 증가시킨다.

인덱스를 지나는 트럭이 있으면 큐에서 poll해주고, (pop) 무게를 onWeight에서 빼준다. 그리고 time을 증가시킨다.
인덱스와 다리길이를 비교하여 조건을 세워주면 다리를 건너는지에 대한 조건을 세울 수 있다?

[java 코드]

근데 야매인 것 같다 .... 시간에서 1씩 차이가 나길래 return + 1 해줬다 ... 테스트 통과하긴 했는데... 밀려오는 죄책감...

바로 return answer해서 해결하는 방법은 없을까. 왜 1만큼 차이가 나지??

그래도 숱한 실패를 거쳐 만든 코드.......... 난 정말...ㅠ

일단 오늘은 여기까지만 보고 내일 한번 더봐야겠다

import java.util.*;

class Solution {
    static class Truck {
        int index;
        int weight;
        
        public Truck(int index, int weight) {
            this.index = index;
            this.weight = weight;
        }
    }
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Queue<Truck> onBridge = new LinkedList<Truck>();
        Queue<Truck> waiting = new LinkedList<Truck>();
        
        int time = 0;
        int onWeight = 0;
        
        for(int i = 0; i < truck_weights.length; i++){
            waiting.add(new Truck(1, truck_weights[i]));
        }
        
        //초기화
        onBridge.add(waiting.peek());
        onWeight += waiting.peek().weight;
        waiting.poll();
        
        while(!onBridge.isEmpty()){
            time++;
            for(Truck truck : onBridge)
                truck.index++;
            
            if(onBridge.peek().index > bridge_length){
                onWeight -= onBridge.peek().weight;
                onBridge.poll();
            }
            
            if(!waiting.isEmpty()){
                int nextWeight = waiting.peek().weight;
                if(onWeight + nextWeight <= weight){
                    onBridge.add(waiting.peek());
                    onWeight += nextWeight;
                    waiting.poll();
                }
            }
           
            
        }
        
        answer = time+1;// 야매..
        //answer = time;
        return answer;
    }
}

 

[java] 

#1. 첫번째 실패 코드

import java.util.*;

class Solution {
    static class Truck {
        int index;
        int weight;
        
        public Truck(int index, int weight){
            this.index = index;
            this.weight = weight;
        }
    }
    
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int onWeight = 0;
        int time = 0;
        
        Queue<Truck> onBridge = new LinkedList<Truck>();
        Queue<Truck> waiting = new LinkedList<Truck>();
        
        int n = truck_weights.length;
        for(int i=0; i<n; i++){
            waiting.add(new Truck(1, truck_weights[i]));
            // 다리에 들어가기 전 기다리는 트럭들
        }
        
        onBridge.add(waiting.peek());
        waiting.poll();
        //이제 다리로 한놈씩 올라갑니다.
        while(!waiting.isEmpty()){
            time++;
            if(onBridge.peek().index > bridge_length){
                onBridge.poll();
                onWeight -= onBridge.peek().weight;
               
            } else {
                onWeight += onBridge.peek().weight;
                int nextWeight = waiting.peek().weight;
                
                if(onWeight + nextWeight > weight){
                    onBridge.peek().index++;
                   
                    break;
                } else{
                    onBridge.add(waiting.peek());
                    onBridge.peek().index++;
                  
                }
            }
            
        }
        answer = time;
        return answer;
    }
}

문제점: 

 

[java 2차시도 코드]

import java.util.*;

class Solution {
    static class Truck {
        int index;
        int weight;
        
        public Truck(int index, int weight){
            this.index = index;
            this.weight = weight;
        }
    }
  
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int onWeight = 0;
        int time = 0;
        
        Queue<Truck> onBridge = new LinkedList<Truck>();
        Queue<Truck> waiting = new LinkedList<Truck>();
        
        int n = truck_weights.length;
        for(int i=0; i<n; i++){
            waiting.add(new Truck(1, truck_weights[i]));
            // 다리에 들어가기 전 기다리는 트럭들
        }
        
       
        onBridge.add(waiting.peek());
        
        //이제 다리로 한놈씩 올라갑니다.
        while(!waiting.isEmpty()){
            if(onBridge.isEmpty()){
                onBridge.add(waiting.peek());
                onWeight += waiting.peek().weight;
                waiting.poll();
            }
            else{
                time++;
            onBridge.peek().index++;
            if(onBridge.peek().index > bridge_length){
                // 길이 초과. 다리를 지나감.
                onBridge.poll();
                onWeight -= onBridge.peek().weight;
            } else {
                int nextWeight = waiting.peek().weight;
                if(onWeight + nextWeight < weight){
                    // 올릴 수 있다.
                    onBridge.add(waiting.peek());
                    onWeight += nextWeight;
                    waiting.poll();
                } else{
                    // 올릴 수 없다.
                    continue;
                }
            }
            
            }
            
        }
        answer = time;
        return answer;
    }
}

코드의 논리성은 올라갔으나 null pointer exception이 발생

-> poll, 순서를 바꿔서 문제 해결

 

논리적인 문제는 해결했으나 distance index 처리 어떻게 해야하나 고민.

queue에서는 각 index를 가져오는 방법이 없어서.

 

[3차시도]

테스트 3개 중 2개 통과.

for문으로 distance index 처리했고, index 증가하는 부분의 순서를 바꿨다.

처리하지 못한 테스트는 남아있는 차 대수만 생각해서. 다리를 지나는 시간까지 생각해야하는데. 

while문의 조건이 잘못되었다. 

-> 자동차 한 대만 다리를 지나가는 경우를 생각하지 못했다. 

import java.util.*;

class Solution {
    static class Truck {
        int index;
        int weight;
        
        public Truck(int index, int weight){
            this.index = index;
            this.weight = weight;
        }
    }
  
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int onWeight = 0;
        int time = 0;
        
        Queue<Truck> onBridge = new LinkedList<Truck>();
        Queue<Truck> waiting = new LinkedList<Truck>();
        
        int n = truck_weights.length;
        for(int i=0; i<n; i++){
            waiting.add(new Truck(1, truck_weights[i]));
            // 다리에 들어가기 전 기다리는 트럭들
        }
        
       
        
        //이제 다리로 한놈씩 올라갑니다.
        while(!waiting.isEmpty()){
            time++;
            if(onBridge.isEmpty()){
                onBridge.add(waiting.peek());
                onWeight += waiting.peek().weight;
                waiting.poll();
              
            }
            else{
              //distance index 처리하는 방법
                for(Truck truck : onBridge){
                    truck.index++;
                }
            if(onBridge.peek().index > bridge_length){
                // 길이 초과. 다리를 지나감.
                onWeight -= onBridge.peek().weight;
                onBridge.poll(); // 순서
            } else {
                int nextWeight = waiting.peek().weight;
                if(onWeight + nextWeight < weight){
                    // 올릴 수 있다.
                    onBridge.add(waiting.peek());
                    onWeight += nextWeight;
                    waiting.poll();
                }
               
            }
            
            }
            
        }
        answer = time;
        return answer;
    }
}

 

[3]

이 코드는 또 그 케이스 빼고 나머지 fail 😂

import java.util.*;

class Solution {
    static class Truck {
        int index;
        int weight;
        
        public Truck(int index, int weight) {
            this.index = index;
            this.weight = weight;
        }
    }
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Queue<Truck> onBridge = new LinkedList<Truck>();
        Queue<Truck> waiting = new LinkedList<Truck>();
        
        int time = 0;
        int onWeight = 0;
        
        for(int i = 0; i < truck_weights.length; i++){
            waiting.add(new Truck(0, truck_weights[i]));
        }
        
        //초기화
        onBridge.add(waiting.peek());
        onWeight += waiting.peek().weight;
        waiting.poll();
        
        while(!onBridge.isEmpty()){
            time++;
            for(Truck truck : onBridge)
                truck.index++;
            
            if(onBridge.peek().index > bridge_length){
                onWeight -= onBridge.peek().weight;
                onBridge.poll();
            }
            
            if(!waiting.isEmpty()){
                int nextWeight = waiting.peek().weight;
                if(onWeight + nextWeight < weight){
                    onBridge.add(waiting.peek());
                    onWeight += nextWeight;
                    waiting.poll();
                }
            }
            
        }
        
        answer = time;
        return answer;
    }
}

조건에서 등호!!!!!

 

[문제 링크]

https://programmers.co.kr/learn/courses/30/parts/12081

프로그래머스