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

다리를 지나는 트럭

문제 설명

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

 

 

풀이

큐를 이용해서 풀었다.

 

감안해야 하는 조건은 현재 다리에 트럭이 올라가 있는 상태에서 다음 트럭이 올라 갈 수 있으면

다음 트럭도 다리에 올리는 메커니즘이다.

 

public static int solution(int bridge_length, int weight, int[] truck_weights)

매개변수로 들어오는 truck_weights에 각 트럭의 무게가 담겨져있다.

 

현재무게 + 다음트럭의무게 <= 다리가 버틸수있는 무게

위의 식을 만족한다면 다리에 올려주면 된다.

 

큐는 2개를 만들었다.

1. 트럭의 무게가 담긴 큐
2. 트럭의 남은 거리가 남은 큐

 

트럭의 무게가 담긴 큐는 왜 필요하냐면 다리위에 올라가 있는 트럭이 목적지 까지 도착을 한다면

현재 다리위에 올라가있는 무게에서 도착한 트럭의 무게를 빼줘야 하기 때문에 필요하다.

 

우선 문제를 풀기 전에 필요한 변수들을 정의 했다.

xxxxxxxxxx
Queue<Integer>bridge = new LinkedList<>(); //차량의 무게를 넣을 것
Queue<Integer>dist = new LinkedList<>();  // 차량별 남은 시간을 넣을 것
int truck_num = 0;
int current_w =0;
int answer = 0;

 

2개의 큐는 위에서 설명한 큐 들이다.

truck_num 이라는 변수는 매개변수로 들어오는 (truck_weight[]) 배열에 접근하기 위한 변수이다.

 

예를들어서 다리 위에 아무런 트럭이 없다고 가정해보자.

그럼 큐에다가 truck_weight[truck_num] 을 하면 1번 트럭이 들어간다.

그 다음 truck_num ++ 을 해주면

truck_num = 1 이므로 2번째 트럭에 접근 할 수 있게 된다.

 

 

문제의 핵심 로직이 담긴 함수이다.

밑에서 차근차근 하나씩 설명해보겠다.

xxxxxxxxxx
       while(true){
           if(bridge.isEmpty() && truck_num == truck_weights.length){
               break;
           }
           if(bridge.isEmpty() && truck_num < truck_weights.length){
               bridge.add(truck_weights[truck_num]);
               dist.add(1);
               current_w = truck_weights[truck_num];
               truck_num++;
               answer++;
               continue;
           }
           
           int size = bridge.size();
​
           for(int i=0; i<size; i++){
               int bridge_w = bridge.poll();
               int bridge_dist = dist.poll();
​
               if(bridge_dist == bridge_length){
                   current_w -= bridge_w;
               }
               else{
                   bridge.add(bridge_w);
                   dist.add(bridge_dist+1);
               }
           }
           if(truck_num <truck_weights.length && current_w + truck_weights[truck_num] <= weight){
               bridge.add(truck_weights[truck_num]);
               dist.add(1);
               current_w += truck_weights[truck_num];
               truck_num ++;
           }
           answer++;
       }

 

 

 

while true문이 끝나는 조건이다.

           if(bridge.isEmpty() && truck_num == truck_weights.length){
               break;
           }

 

bridge는 다리위에 올라가있는 트럭의 무게들이 들어있는 큐 이다.

다리위에 올라가 있는 트럭이 없고

truck_num == truck_weights.length는 모든 트럭을 다 순회 했다는 뜻이다.

 

 

그 다음 로직을 살펴보자

 

           if(bridge.isEmpty() && truck_num < truck_weights.length){
               bridge.add(truck_weights[truck_num]);
               dist.add(1);
               current_w = truck_weights[truck_num];
               truck_num++;
               answer++;
               continue;
           }

이건 다리위에 아무런 트럭이 없을 경우에 다리위에 트럭을 올려주는 것이다.

truck_num으로 트럭을 차례대로 접근하면서

bridge 큐에는 트럭의 무게를 , dist 큐에는 다리위에 올라간 시작거리를 넣어주는 것이다.

그리고 다리위에 아무것도 없는 상태였다가 하나의 트럭이 올라갔으니

current_w 를 현재 트럭의 무게로 대입해준다.

그리고 다음 트럭으로 접근하기 위해서 truck_num을 1 증가시켜주고

answer라는 시간을 측정하는 변수 또한 증가시켜준다.

 

 

그 다음 로직이다. 위에서 다리위에 아무것도 없을때 트럭을 넣어줬는데 그럴 경우 continue로 해당 부분이 실행이 안된다.

 

이 아래 로직부턴 다리위에 1개이상의 트럭이 존재 할 때 실행되는 코드이다.

​
           int size = bridge.size();
           for(int i=0; i<size; i++){
               int bridge_w = bridge.poll();
               int bridge_dist = dist.poll();
​
               if(bridge_dist == bridge_length){
                   current_w -= bridge_w;
               }
               else{
                   bridge.add(bridge_w);
                   dist.add(bridge_dist+1);
               }
           }

다리위에 올라가있는 트럭의 갯수만큼 반복문을 순회하는데

bridge_w 는 트럭의 무게, bridge_dist는 트럭의 다리위에서의 거리 이다.

 

현재 트럭의 다리위에서 거리가 문제에서 주어진 다리 길이의 끝부분에 도달했다면

현재무게에서 빼준다. 이 경우 트럭이 도달 한 것이다.

 

그렇지 않을 경우 해당하는 트럭을 다시 큐에 넣어주는데 다리위에서의 거리를 1칸 증가 시켜준다.

 

 

마지막 로직 다리위에 1개이상의 트럭이 있고 다음 트럭이 다리위로 올라갈수 있을때

           if(truck_num <truck_weights.length && current_w + truck_weights[truck_num] <= weight){
               bridge.add(truck_weights[truck_num]);
               dist.add(1);
               current_w += truck_weights[truck_num];
               truck_num ++;
           }

 

if문에 있는 truck_num < truck_weights.length 가 없으면 인덱스 오류가 나기때문에 조건을 꼭 추가해줘야한다.

(왜 그런지는 스스로 생각해보길 바란다.)

다리위에 트럭을 올리고 현재 다리의 무게또한 증가시켜주면 된다.

 

 

전체코드

import java.util.*;
class Solution {
    // bridge length = 다리길이 / weight = 다리무게 / truck_weights 대기트럭의무게
    public  int solution(int bridge_length, int weight, int[] truck_weights) {
       Queue<Integer>bridge = new LinkedList<>(); //차량의 무게를 넣을 것
       Queue<Integer>dist = new LinkedList<>();  // 차량별 남은 시간을 넣을 것
       int truck_num = 0;
       int current_w =0;
       int answer = 0;
       while(true){
           if(bridge.isEmpty() && truck_num == truck_weights.length){
               break;
           }
           if(bridge.isEmpty() && truck_num < truck_weights.length){
               bridge.add(truck_weights[truck_num]);
               dist.add(1);
               current_w = truck_weights[truck_num];
               truck_num++;
               answer++;
               continue;
           }
           
           int size = bridge.size();
           
           for(int i=0; i<size; i++){
               int bridge_w = bridge.poll();
               int bridge_dist = dist.poll();
​
               if(bridge_dist == bridge_length){
                   current_w -= bridge_w;
               }
               else{
                   bridge.add(bridge_w);
                   dist.add(bridge_dist+1);
               }
           }
           if(truck_num <truck_weights.length && current_w + truck_weights[truck_num] <= weight){
               bridge.add(truck_weights[truck_num]);
               dist.add(1);
               current_w += truck_weights[truck_num];
               truck_num ++;
           }
           answer++;
       }
       return answer;
   }
}