[프로그래머스 LV2] 다리를 지나는 트럭(Queue, 큐)

🧐 프로그래머스 LV2. 다리를 지나는 트럭

문제 설명

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

 

💡 문제 풀이

다리에 오르지 않은 트럭 Queue, 다리를 지나가고 있는 트럭 Queue 2개를 사용해서 문제를 풀 수 있었다.

 

필요한 클래스와 변수부터 정의해준다.

다리를 지나는 트럭은 무게와 지나고 있는 위치를 알고 있어야 하므로 클래스로 정의해준다.

Queue<Integer> queue = new LinkedList<>(); // 대기 중인 트럭
Queue<Truck> bridgeQueue = new LinkedList<>(); // 다리를 지나는 트럭

for (int truck_weight : truck_weights) { // 대기 중인 트럭 Queue 초기화
	queue.add(truck_weight);
}

int sum = 0, time = 0; // 다리 위의 트럭 무게 합, 경과한 시간

private class Truck {
	int weight; // 트럭 무게
	int pos; // 지나고 있는 위치
        
	Truck(int weight, int pos) {
		this.weight = weight;
		this.pos = pos;
	}
}

 

2개의 큐가 빌 때까지 반복문을 실행한다.

while (!queue.isEmpty() || !bridgeQueue.isEmpty()) {
	if (!bridgeQueue.isEmpty()) { // 다리를 지나는 트럭이 있으면
		Truck truck = bridgeQueue.peek();
		if (truck.pos == bridge_length) {
			bridgeQueue.poll();
			sum -= truck.weight; // 다리 위 트럭 무게 합 업데이트
   		}
        
		while(!bridgeQueue.isEmpty()) { // 다리 위에 남아있는 트럭 위치 업데이트
			Truck t = bridgeQueue.poll();
			bridgeQueue.add(new Truck(t.weight, t.pos + 1));
		}
	}
            
	if (!queue.isEmpty()) { // 대기 중인 트럭이 있으면
		int next = queue.peek();
		if (bridgeQueue.size() < bridge_length && sum + next <= weight) { // 다리 상황
			bridgeQueue.add(new Truck(next, 1));
			queue.poll();
			sum += next; // 다리 위 무게 합 업데이트
		}
	}
            
	time++; // 시간 경과
}

다리를 지나는 트럭이 있으면 먼저 처리해준다.

가장 처음 다리를 올라온 트럭의 위치가 다리 끝에 닿았으면 큐에서 꺼낸다. (다리 위 트럭 무게 합 업데이트 필요)

대기 중인 트럭이 있고, 다음 트럭이 다리를 지날 수 있으면(트럭 개수가 다리 길이 이하이고, 들어 온 트럭 포함 무게 합을 버틸 수 있음) 다음과 같이 처리한다.

대기 중인 트럭을 큐에서 꺼내고, 다리를 지나는 큐에 삽입한다. (다리 위 무게 합 업데이트 필요)

 

위 풀이 방식을 전체 코드로 풀어내면 아래와 같다.

import java.util.*;

class Solution {
    private class Truck {
        int weight;
        int pos;
        
        Truck(int weight, int pos) {
            this.weight = weight;
            this.pos = pos;
        }
        
        @Override
        public String toString() {
            return "(" + this.weight + " " + this.pos + ")";
        }
    }
    
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> queue = new LinkedList<>();
        for (int truck_weight : truck_weights) {
            queue.add(truck_weight);
        }
        
        Queue<Truck> bridgeQueue = new LinkedList<>();
        int sum = 0, time = 0;
        
        while (!queue.isEmpty() || !bridgeQueue.isEmpty()) {
            if (!bridgeQueue.isEmpty()) {
                Truck truck = bridgeQueue.peek();
                if (truck.pos == bridge_length) {
                    bridgeQueue.poll();
                    sum -= truck.weight;
                }
                int size = bridgeQueue.size();
                while(size-- > 0) {
                    Truck t = bridgeQueue.poll();
                    bridgeQueue.add(new Truck(t.weight, t.pos + 1));
                }
            }
            
            if (!queue.isEmpty()) {
                int next = queue.peek();
                if (bridgeQueue.size() < bridge_length && sum + next <= weight) {
                    bridgeQueue.add(new Truck(next, 1));
                    queue.poll();
                    sum += next;
                }
            }
            
            time++;
        }

        return time;
    }
}

 

✨ 포스팅을 마치며

Queue를 사용하는 문제는 구현 유형이 섞인 케이스가 많은 것 같다.