제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.
포인트
다리를 큐로 표현해 각 트럭의 상태를 관리하며, 트럭이 다리를 건너는 동안의 시간과 다리의 무게 제한을 고려해 순차적으로 트럭을 다리에 올리고 내립니다. 반복문은 트럭이 모두 다리를 건널 때까지 계속됩니다.
소스코드
import java.util.*;
class Solution {
static class Truck {
int weight, position;
public Truck(int weight) {
this.weight = weight;
this.position = 0;
}
public Truck(int weight, int position) {
this.weight = weight;
this.position = position;
}
}
public int solution(int bridge_length, int weight, int[] truck_weights) {
int time = 0; // 경과 시간
int bridgeWeight = 0; // 현재 다리 위의 트럭 총 무게
Queue<Truck> bridge = new LinkedList<>(); // 다리 위의 트럭 큐
int idx = 0; // 대기 트럭 인덱스
while (idx < truck_weights.length || !bridge.isEmpty()) {
time++;
if (!bridge.isEmpty()) {
Truck frontTruck = bridge.peek(); // 맨 앞의 트럭
if (time - frontTruck.position >= bridge_length) { // 다리를 다 건넜을 경우
bridgeWeight -= frontTruck.weight; // 다리 무게에서 제외
bridge.poll(); // 트럭 다리에서 내림
}
}
if (idx < truck_weights.length) {
if (bridgeWeight + truck_weights[idx] <= weight && bridge.size() < bridge_length) {
bridge.add(new Truck(truck_weights[idx], time)); // 트럭 다리에 올림
bridgeWeight += truck_weights[idx]; // 현재 다리 무게 갱신
idx++; // 대기 트럭 인덱스 증가
}
}
}
return time;
}
}코드 설명
- Truck 클래스
- weight: 트럭의 무게.
- position: 트럭이 다리를 건너기 시작한 시점(시간).
- 변수 초기화:
- time: 전체 시뮬레이션의 경과 시간을 나타냅니다.
- bridgeWeight: 현재 다리 위에 있는 트럭들의 총 무게입니다.
- bridge: 현재 다리를 건너고 있는 트럭들을 저장하는 큐입니다.
- idx: 대기 중인 트럭을 가리키는 인덱스입니다.
- 메인 로직:
- 시간 증가: 매 반복마다 time이 증가합니다. 이는 시뮬레이션의 한 단계를 의미합니다.
- 트럭 이동:
- bridge 큐에서 맨 앞에 있는 트럭(frontTruck)의 위치를 확인합니다.
- time - frontTruck.position이 bridge_length보다 크거나 같다면, 트럭은 다리를 건넜으므로 bridge.poll()로 큐에서 제거하고, bridgeWeight에서 트럭의 무게를 뺍니다.
- 새 트럭 추가:
- 아직 다리를 건너지 않은 트럭이 있을 경우(idx < truck_weights.length), 현재 다리의 무게(bridgeWeight + truck_weights[idx])가 제한을 초과하지 않고 다리 길이 조건을 만족하면 새 트럭을 bridge에 추가합니다.
- 새 트럭이 다리에 추가되면 bridgeWeight를 업데이트하고 idx를 증가시켜 다음 트럭을 가리킵니다.
- 종료 조건:
- 대기 중인 트럭이 더 이상 없고(idx >= truck_weights.length), bridge에 남아 있는 트럭도 없을 때 시뮬레이션이 종료됩니다.
- 결과 반환:
- 최종적으로 경과된 time을 반환합니다. 이는 모든 트럭이 다리를 건너기까지 걸린 총 시간입니다.
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
| [코딩테스트] Java 디스크 컨트롤러 (1) | 2024.11.11 |
|---|---|
| [코딩테스트] Java 더 맵게 (1) | 2024.11.11 |
| [코딩테스트] Java 주식가격 (1) | 2024.11.09 |
| [코딩테스트] Java 프로세스 (1) | 2024.11.09 |
| [코딩테스트] Java 올바른 괄호 (0) | 2024.11.09 |