프로그래머스 다리를 지나는 트럭 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

 

 

---

소스코드

import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
public class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Queue<Integer> q = new ConcurrentLinkedQueue<>();
        int sum = 0;
        for(int t : truck_weights) {
            while(true) {
                if(q.isEmpty()) {
                    q.add(t);
                    sum += t;
                    answer++;
                    break;
                } else if(q.size() == bridge_length) {
                    sum -= q.poll();
                } else {
                    if(sum + t > weight) {
                        answer++;
                        q.add(0);
                    } else {
                        q.add(t);
                        sum+=t;
                        answer++;
                        break;
                    }
                }
            }
        }
        return answer + bridge_length;
    }
}

 

 

설명

처음엔 배열로 풀어볼까 하다가 꼬이는 거 같아서.. 다른 방향으로 생각해보았다.

"트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. "라는 문장에서 Queue를 생각해냈다.

다리를 하나의 Queue객체로 생각을 하고 이 Queue에 조건을 걸어 트럭이 진입하고 빠져나가는 식으로 코딩했다.

 

우선 Queue객체를 생성해준다.

forEach를 통해 트럭의 수만큼 반복한다.

 

첫 번째 조건은 Queue가 비어있는 경우다. 

이 경우에는 트럭이 무조건 진입가능 하기 때문에 바로 큐에 add()해주고

다리 위 트럭들의 무게를 의미하는 sum변수에 진입한 트럭의 무게를 더해준다.

시간(초)을 의미하는 answer도 트럭이 진입했기 때문에 1을 더해준다.

 

두 번째 조건은 Queue객체의 사이즈가 다리의 길이와 같은 경우다.

이 경우는 Queue가 가득차 있다는 의미이며 동시에 가장 먼저 진입한 트럭이 다리의 끝자락에 다다랐다는 의미기도 하다.

그렇기 때문에 이 트럭을 다리 밖으로 지나가게 하기 위해 poll() 메서드를 이용한다.

그리고 다리 위 트럭들의 무게를 의미하는 변수 sum에서 다리를 빠져나간 트럭의 무게를 빼준다.

 

세 번째 조건은 위 두 조건에 해당하지 않은 경우다. 즉 트럭이 다리 위에 있지만 Queue가 가득 차 있지 않은 상태이다.

이 때는 이미 다리 위의 있는 트럭들의 무게와 새롭게 진입할 트럭의 무게의 합이 weights(다리가 버틸 수 있는 무게)를 초과하는지 아닌지 조건을 검사한다.

만약 weights보다 크다면 새로운 트럭은 진입할 수 없다 그렇기 때문에 Queue에는 0을 넣어서 이미 Queue에 있는 트럭이 혼자 다리를 지나가도록 해준다.

 

그렇지 않고 weights보다 작다면, 새로운 트럭이 진입할 수 있다. 이 때는 첫 번째 조건과 마찬가지로 Queue에 새로 진입할 트럭을 넣어주고 sum에 새롭게 진입한 트럭의 무게를 더해준다. 

 

모든 트럭들이 다리에 진입하고 이 다리를 모두 지나가야 하기 때문에 다리의 길이만큼 answer에 더해준 다음 리턴해준다.