[Programmers/JAVA] 다리를 지나는 트럭

 

내 코드

 

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        
        //queue 선언
        Queue<Integer> q=new LinkedList<>();

        int sum=0;
        int index=0;
        
        while(index!=truck_weights.length) {
            if(q.size()==bridge_length) { // 다리길이만큼 트럭이 차면
                sum-=q.remove(); //맨 앞에 있던 트럭 도착지로 빼주기 + sum에서도 제거
            }
            if(sum+truck_weights[index]>weight) {
                q.offer(0); // 다리의 빈 공간에 0을 추가해주기
                answer++;
            }else {
                sum+=truck_weights[index];
                q.offer(truck_weights[index]);
                answer++;
                index++;
            }
        }
        answer+=bridge_length;
        
        return answer;
    }
}

 

느낀점

몇시간동안 끙끙 대다가... 내 우선순위는 무엇일까? 하는 생각이 들었다. 알고리즘을 내 힘으로 온전히 풀어내는것은 내 우선순위가 아니라는 생각이 들었다. 그래서 결국 다른 사람이 풀은 걸 참고했는데 그 중에서 내가 제일 이해하기쉬운 방법을 가져왔다. 그것은!! 다리의 빈 자리에 "0" 을 추가해주는 것이었다. 그렇게 되면 q는 다리의 길이만큼의 사이즈를 계속해서 유지하면서, 걸리는 시간을 제대로 잴 수 있기 때문이다.

이 알고리즘을 짜고 난 후 더 간단하게 고칠 수 있을 것 같아 손을 봐봤는데 실패했다. 나는 다음 트럭의 무게가 다리가 버틸 수 있는 무게를 넘었을 경우 bridge_length만큼 answer에 더해주면 될 것이라 생각했다. 그 후엔 q.clear().

하지만 내가 간과한것은 트럭이 끊이지않고 계속해서 들어온다는 것이었다... 다리에 들어와있는 트럭의 무게가 weight을 넘기더라도 시간이 지나면 선두의 트럭은 도착해서 다리에서 내려갈 테고, 다리에 남은 트럭과 다음 들어올 트럭의 합이 weight을 안 넘길 수 있다는 것을 간과한것임..ㅜㅜ 하여간 은근히 어려운 문제였다.