[Programmers] #14 다리를 지나는 트럭 [JAVA]

다리를 지나는 트럭

 

 

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

 

 

 

 

1. 문제 설명

 

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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 함수를 완성하세요.

 

 

 

2. 나의 코드

 

- 지나기 전 트럭이 담긴 큐와 다리위에 있는 트럭이 담긴 큐를 만든다.

- 트럭을 하나씩 넣으면서, if문을 사용하여 tot_weight이 weight보다 큰지 아닌지 판별한다.

- while문 한번 돌때마다 time을 하나씩 늘려준다.

- 마지막 while을 빠져나올때 time++을 해준다. 마지막 트럭의 time이 0경우 time++을 하지 않고 그냥 빠져나오기 때문이다.

 

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int tot_weight = 0;
        int time = 0;
        
        Queue  q = new LinkedList<>();
        Queue  q2 = new LinkedList<>();

        Truck [] trucks = new Truck [truck_weights.length];

        for(int i=0; i < trucks.length;i++){
            trucks[i] = new Truck(bridge_length, truck_weights[i]);
            q.offer(trucks[i]);
        }

        tot_weight += q.peek().weight;
        q2.offer(q.poll());

        while(!q2.isEmpty()){
            for(Truck truck : q2){
                truck.time--;
            }

            if(q2.peek().time < 0){
                tot_weight -= q2.poll().weight;
            }

            if(!q.isEmpty() && tot_weight + q.peek().weight <= weight){
                tot_weight += q.peek().weight;
                q2.offer(q.poll());
            }
            time++;
        }
        return answer=time;
    }
}

class Truck {
    int time;
    int weight;

    public Truck(int time, int weight){
        this.time = time;
        this.weight = weight;
    }
}

 

 

 

 

3. 나의 실패한 코드들

 

1) Truck 배열을 이용한 코드

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int w = 0;
        int wind = 0;
        int time=0;

        Truck [] t = new Truck[truck_weights.length];

        for(int i =0; i<truck_weights.length; i++){
        	t[i] = new Truck(bridge_length,truck_weights[i]);
        }

        for(int k = 0 ; k < t.length ; k++){
        	if(w +t[k].weight <= weight){
        		w += t[k].weight;
        		for(int i = wind; i<k; i++){
        			t[i].time--;
        			if(t[i].time == 0){
        				w-=t[i].weight;
        				wind++;
        			}
        		}
        		time++;
        	}
        	else{
        		while(w +t[k].weight > weight){
        			for(int i = wind;i<k;i++){
        				t[i].time--;
        				if(t[i].time == 0){
        					w-=t[i].weight;
        					wind++;
        				}
        			}
        			time++;
        		}

    			w+=t[k].weight;
        		t[k].time--;
        	}
        
    	}

    while(wind != t.length){
        	for(int i = wind;i<t.length;i++){
        		t[i].time--;
        		if(t[i].time == 0){
        			w-=t[i].weight;
        			wind++;
        		}
        	}
        	time++;
        }

        return answer=time;
    }
}

class Truck{
	int time;
	int weight;

	public Truck(int time, int weight){
		this.time = time+1;
		this.weight = weight;
	}
}

 

 

 

 

2) ArrayList를 이용한 풀이

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int w = 0;
        int wind = 0;
        int time=0;

        Truck [] t = new Truck[truck_weights.length];

        for(int i =0; i<truck_weights.length; i++){
        	t[i] = new Truck(bridge_length,truck_weights[i]);
        }

        for(int k = 0 ; k < t.length ; k++){
        	if(w +t[k].weight <= weight){
        		w += t[k].weight;
        		for(int i = wind; i<k; i++){
        			t[i].time--;
        			if(t[i].time == 0){
        				w-=t[i].weight;
        				wind++;
        			}
        		}
        		time++;
        	}
        	else{
        		while(w +t[k].weight > weight){
        			for(int i = wind;i<k;i++){
        				t[i].time--;
        				if(t[i].time == 0){
        					w-=t[i].weight;
        					wind++;
        				}
        			}
        			time++;
        		}

    			w+=t[k].weight;
        		t[k].time--;
        	}
        
    	}

    while(wind != t.length){
        	for(int i = wind;i<t.length;i++){
        		t[i].time--;
        		if(t[i].time == 0){
        			w-=t[i].weight;
        			wind++;
        		}
        	}
        	time++;
        }

        return answer=time;
    }
}

class Truck{
	int time;
	int weight;

	public Truck(int time, int weight){
		this.time = time+1;
		this.weight = weight;
	}
}

 

 

 

 

4. 보완

 

12시간 걸렸다... 알고리즘 구현 능력이 너무 부족하다는 것을 느낀다.

머리로 하나씩 생각해보는 능력이 부족하다. 특히 하나씩 값이 늘어나거나 줄어들때, 꼭 1정도 오차가 생긴다.

꼼꼼하게 코딩하는 능력을 길러야 할 것 같다.