사용 알고리즘: 큐
사용 언어: java
import java.io.*;
import java.util.*;
/**
"순서대로"
처음에서 들어갈 땐 +1, 마지막에서 나갈 땐 시간 증가 없음
*/
// https://minhamina.tistory.com/241
// 0을 집어 넣기
// 다리를 queue로 만드는 거 까지는 생각했는데...
class Solution {
//queue의 길이 == bridge_length
//queue 안에 있는 값의 합이 weight 초과하면 안 됨
//truck_weights 순서대로 움직임(변수 idx를 두고 관리)
//더 올라올 수 없으면 queue.add(0) 하기
//뭐든 올라올 때마다 time++;
// 내려갈 때는 time 변화 x
public int solution(int bridge_length, int weight, int[] truck_weights) {
Queue<Integer> bridge = new ArrayDeque<>();
int time = 0;
int idx = 0; // truck_weights.length 미만이어야 함
int sum = 0; //순간마다 다리에 올라간 무게 합 구하려면 시간 오래 걸리니까 여기에 저장
while(idx < truck_weights.length) {
if(bridge.isEmpty()) {
sum += truck_weights[idx];
bridge.add(truck_weights[idx++]);
time++;
}
if(idx >= truck_weights.length) break;
if(bridge.size() >= bridge_length) {
sum -= bridge.poll();
}
//올라갈 수 있는데
//무거워서 못 올라갈 때
if(sum + truck_weights[idx] > weight) {
bridge.add(0);
time++;
}
//가벼워서 더 올라갈 수 있을 때
else {
sum += truck_weights[idx];
bridge.add(truck_weights[idx++]);
time++;
}
}
//마지막 애는 올라만 갔으니까 '다리 길이'만큼 더해주기
return time + bridge_length;
}
}
인사이트:
다리에 큐를 써야 하는 건 인지함,
트럭이 더 올라가지 않고 시간만 가야하는 경우 어떻게 처리할지 생각 못 함 => 큐에 0을 넣으면 된다.
=> 0 활용
'알고리즘 > 프로그래머스' 카테고리의 다른 글
** 섬 연결하기 (0) | 2024.03.07 |
---|---|
큰 수 만들기 * (1) | 2024.02.29 |
** 큰 수 만들기** (0) | 2024.02.26 |
등굣길 다시 풀어보기 - 왜 효율성 테스트에서 통과가 안 되는가 -> 맵 확인용 출력 때문에 그랬다고 한다 (0) | 2024.02.21 |
전화번호 목록 (0) | 2024.02.21 |