🔍 정답까지의 과정
일단 문제에서 사용하는 것이 스택/큐라는 것을 보고 들어가버려서 큐나 스택을 응용하려고 했다.
다리에 먼저 진입한 트럭이 먼저 나오게 되니까 큐를 이용해야한다고 생각했지만 결론적으로 나에게 가장 어려웠던 부분은 이미 달리고 있는 트럭들이 해당 초가 되면 나와야할텐데 그걸 어떻게 구현할지에 대한 고민이 가장 컸다.
방법1은 클래스로 만들어서 <트럭무게, 현재 시간> 이런식으로 관리를 하려고 했는데 그럼 다리에 있는 트럭들 모두를 반복문마다 계산을 해줘야한다..이렇게는 풀면 안되겠다고 생각했고
다음 방법들을 생각하려고 했는데 도저히 이미 달리고 있는 트럭들이 제 시간에 큐에서 remove하는 방법을 못 생각해냈고 검색을 했다..
💡 아이디어
그럼 이미 풀이를 하신 분들은 어떻게 트럭들을 관리하셨을까?
큐를 이용해서 트럭을 관리하는 것은 맞았는데
상황을 세분화하여 코드 작성
- 큐 Empty
- 큐 Size == 다리의 길이
- 큐 Size < 다리 길이
이렇게 경우를 나누고 풀이를 하시는 것을 볼 수가 있었는데 이때까지만 해도 아니 이렇게 해서 어떻게 이미 들어간 트럭들을 관리할 수 있지 라는 생각을 했는데.. 2번에 큐의 크기가 다리의 길이가 된다. 이 부분에서 설명이 가능했다. 3번과 연계되는데 7,4,5,6의 상황에서
(1) 큐에 먼저 7이 들어갈 것이고
(2) 다음 조건은 큐 크기(1) < 다리 길이(2)
(3) 이때 현재 다리 하중이 견딜 수 있다면 트럭을 하나 더 진입 시킨다(que.add())
그런데 만약 하중이 견딜 수 없는. 10Kg를 버틸 수 있는데 이미 7Kg가 들어가있고 4Kg가 다음이라면 당연히 다리가 무너지니까 트럭이 진입할 수 없다 이 때 0Kg을 그냥 큐에 삽입한다!
이렇게 되면 큐는 7,0이 들어가게 되고 다음 조건은 2에서 걸리게 된다! 이 때에는 먼저 들어간 7은 빼주고 다리의 현재 하중을 갱신시킨다!
💬 회고
내가 풀이를 하면서 느낀 것은 완벽히 해결한 문제다! 이런 건 아닌 것 같다..생각지도 못한 풀이들이 적용되고 이해는 하는데 내 방식이 아니라 해야하나? 새로운 방식이어서 그런 것 같긴한데 핵심적인 2가지!
- 들어간 트럭이 다리를 다 건넜다는 것을 (큐 크기 == 다리 길이)로 표현
- 큐에 들어간 트럭의 무게가 상한이 되어 더 못 넣을 때 0을 넣으면서 큐를 관리하는 것
이 2가지를 생각조차 하지 못한 부분이었다.
1초에 길이1씩 이동하니까 더 트럭이 진입하지 못한다면 0Kg 트럭(사실 없는 트럭)을 넣어서 큐를 관리하다가 큐 크기와 다리 길이가 같아진다면 트럭을 다리 넘어로 통과시키는..이런 식에 0을 넣어서 큐를 관리하는 방법도 꼭 기억하자!
💻 성공 코드
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
Queue<Integer> curTruckNum = new LinkedList<>();
int answer = 0;
int sum = 0;
//트럭들 1개씩 꺼내서 처리
for(int i= 0 ; i< truck_weights.length; i++){
int curKg = truck_weights[i];
while(true){
//다리가 비어있다(큐 Empty)
if(curTruckNum.isEmpty()){
curTruckNum.add(curKg);
sum += curKg;
answer++;
break;
}
//도착한 트럭이 있다(트럭 수 == 다리의 길이)
else if(curTruckNum.size() == bridge_length){
sum -= curTruckNum.poll();
}
//현재 지나는 트럭이 있고 도착한 트럭도 없다(1.트럭 진입 가능 2.트럭 진입 불가)
else{
//지금 트럭 넣어도 하중 버틸 수 있다면
if(curKg + sum <= weight){
sum += curKg;
curTruckNum.add(curKg);
answer++;
break;
}
//못 버티면 트럭 더 넣지말고 공기 같은 0Kg을 넣자!
else{
curTruckNum.add(0);
answer++;
}
}
}
}
return answer + bridge_length;
}
}