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

문제

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

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

따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.

 

풀이방법

1.다리가 비어있을 때 -> truck_weights 배열의 첫번째 트럭을 큐와 Sum에 추가해준다.

2.다리의 길이가 올라가 있는 트럭의 대수와 같을 때 (여기선 2가지 경우로 나뉘어진다)

2-1.다음 트럭이 올라가도 무게를 초과하지 않을 때 -> 큐에 저장된 값을 빼고 Sum에서 빼준다.

2-2.다음 트럭이 올라가면 무게가 초과할 때 -> 큐에 0값을 추가 해 준다.

 

나의 풀이

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

 

다른 사람의 풀이

import java.util.*;
 
class Solution {
    class Truck {
        int weight;
        int move;
 
        public Truck(int weight) {
            this.weight = weight;
            this.move = 1;
        }
 
        public void moving() {
            move++;
        }
    }
 
    public int solution(int bridgeLength, int weight, int[] truckWeights) {
        Queue<Truck> waitQ = new LinkedList<>();
        Queue<Truck> moveQ = new LinkedList<>();
 
        for (int t : truckWeights) {
            waitQ.offer(new Truck(t));
        }
 
        int answer = 0;
        int curWeight = 0;
 
        while (!waitQ.isEmpty() || !moveQ.isEmpty()) {
            answer++;
 
            if (moveQ.isEmpty()) {
                Truck t = waitQ.poll();
                curWeight += t.weight;
                moveQ.offer(t);
                continue;
            }
 
            for (Truck t : moveQ) {
                t.moving();
            }
 
            if (moveQ.peek().move > bridgeLength) {
                Truck t = moveQ.poll();
                curWeight -= t.weight;
            }
 
            if (!waitQ.isEmpty() && curWeight + waitQ.peek().weight <= weight) {
                Truck t = waitQ.poll();
                curWeight += t.weight;
                moveQ.offer(t);
            }
        }
 
        return answer;
    }
}

출처: 프로그래머스 코딩 테스트 연습 https://programmers.co.kr/learn/challenges