💡 문제 - 다리를 지나는 트럭
문제 설명
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순서로 건너려 합니다.
모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다.
다리에는 트럭이 최대 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] | 110 |
💡 풀이
public int solution(int bridge_length, int weight, int[] truck_weights) {
int time = 0; // 다리를 건너는 데 걸린 시간
int current_weight = 0; // 현재 다리 위에 있는 트럭들의 무게 합
Queue<Integer> bridge = new LinkedList<>(); // 다리 위의 트럭들을 관리할 큐
// 각 트럭에 대해 처리
for (int truck : truck_weights) {
while (true) {
// 다리에 올라간 트럭 수가 다리 길이와 같으면 트럭이 다리를 다 건넜다는 의미
if (bridge.size() == bridge_length) {
current_weight -= bridge.poll(); // 다리에서 트럭을 내리고 무게를 갱신
}
// 현재 트럭을 다리에 올릴 수 있는지 확인
if (current_weight + truck <= weight) {
bridge.add(truck); // 트럭을 다리에 올림
current_weight += truck; // 현재 무게를 갱신
time++; // 시간을 증가
break; // 다음 트럭으로 넘어가기 위해 루프 탈출
} else {
// 무게 초과로 트럭을 올릴 수 없을 때는 시간을 1초 추가하고
// 다리에 0을 추가하여 트럭이 지나가도록 함
bridge.add(0); // 무게 초과이므로 빈 공간을 추가
time++; // 시간을 증가
}
}
}
// 마지막 트럭이 다리를 완전히 건너는 시간 추가
time += bridge_length;
return time;
}문제 접근 방식
이 문제는 트럭들이 순서대로 다리를 건너는 동안 각 트럭의 무게와 다리의 최대 무게, 다리의 길이를 고려하여 최소 시간을 계산하는 문제입니다.
트럭들은 큐(Queue)를 사용하여 다리 위에 올라가고, 다리의 길이와 무게 제한을 넘지 않도록 주의해서 푸는 문제.
Queue를 사용하는 이유
선입선출(FIFO, First-In-First-Out) 구조를 가지는 자료구조로,
가장 먼저 삽입된 요소가 가장 먼저 제거됩니다.
주요 특징
선입선출(FIFO) 원칙 : 가장 먼저 삽입된 요소가 가장 먼저 제거됨.
기본 연산:
enqueue: 요소를 큐의 뒤에 삽입.
dequeue: 요소를 큐의 앞에서 제거.
peek: 큐의 앞에 있는 요소를 제거하지 않고 조회.
사용 예: 트럭이 다리를 건너는 순서 관리, 프로세스 스케줄링, 너비 우선 탐색(BFS) 등
문제에서 먼저 다리에 올라간 트럭이 다리를 건너야한다. (선입선출)
그러므로 Stack(후입선출)은 사용할 수 없다.
풀이 설명
1. 변수 설정:
time은 트럭들이 다리를 건너는 데 걸리는 총 시간을 저장한다.
current_weight은 현재 다리 위에 있는 트럭들의 무게 합을 저장한다.
bridge는 다리 위의 트럭들을 관리하기 위해 큐(Queue)로 선언한다.
2. 트럭 처리:
각 트럭을 순차적으로 처리하며, 트럭을 다리에 올릴 수 있는지 확인합니다.
트럭을 다리에 올릴 수 있는 경우, 트럭을 다리에 추가하고 무게를 갱신합니다.
트럭을 올릴 수 없는 경우, 시간을 1초 추가하고 큐에 0을 추가하여 트럭이 다리를 건널 수 있도록 합니다.
3. 마지막 트럭 처리:
모든 트럭이 다리를 건넌 후, 마지막 트럭이 다리를 완전히 건너는 시간을 추가합니다.
