다리를 지나는 트럭 (for JAVA)

일단 이문제는 큐를 이용해야 하는 문제라 linkedList를 사용해야 한다 1시간 이상 무조건 넘어가면 극도로 피곤해지므로 알고리즘이 확연히 떠오르지 않아서 몇번 검색 해서 찾아보았다

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int sum = 0;
        LinkedList<Integer> ll = new LinkedList<Integer>();
        for(int i = 0; i < truck_weights.length; i++) {
            int truck = truck_weights[i];
            while(true) {
                if (ll.isEmpty()) {
                    ll.add(truck);
                    answer++;
                    sum += truck;
                    break;
                } else if (ll.size() == bridge_length) {
                    sum -= ll.poll();
                } else if (sum + truck > weight) {
                    ll.add(0);
                    answer++;
                } else {
                    ll.add(truck);
                    answer++;
                    sum += truck;
                    break;
                }
            }
        }
        return answer + bridge_length;
    }
}

일단 이 답안의 코드 설명은 어디에나 다 나와있는 것이고 이것이 그렇게 중요하다 생각하지 않는다.

이문제에서 가장 주목해야 한다고 생각하는건 while 안에 있는 if문의 순서다 모두가 알다시피 ifelse문은 여러가지 문맥이 있지만 단 한군대만 들리고 나머지가 해당되더라도 처음에 해당되는 해당되는 문이 아니라면 내용을 실행하지 않고 넘어간다는 점이다.

  1. 실행하고 있는 큐가 비어있는지 ?
    => 비어있다면 큐에 넣고 시간을 1초 흐르게 한뒤 현재 큐에 있는 무게를 더한후 다음에 실행할 트럭에 포커스를 할 수 있도록 break 한다.
  2. 큐의 길이가 다리의 길이와 같다 ?
    2-1. 다리의 길이 만큼 1초에 이동을 해야 함으로 큐의 길이 만큼 갔다는 것은 가장 앞쪽에 있던 트럭이 마지막 경로에 도달했다는 것을 알 수 있다.
    2-2. 이것을 위해 3을 하게된다
  3. 트럭의 무게에 현재 큐 무게를 더하면 다리의 하중 보다 크다?
    => 시간을 1초 흐르게 한뒤, 큐에 0을 더한다 (0을 더하는 이 행위는 2-1을 위함이다)
  4. 다리의 하중이 현재 큐의 무게와 트럭의 무게를 견딘다
    => 시간을 1초 흐르게 하고 큐에 트럭의 무게를 더하고 큐의 현재무게에 트럭의 무게를 더해준후 다음 트럭에 포커스를 할 수 있도록 break한다

이 내용들은 큐이기 때문에 이 실행순서로 작동해야 한다.
이것은 어떤 풀이든 간에 이 순서로밖에 진행할 수 없는 것이다.
특히 저 0을 offer 하는 것은 정말 충격이었다. 이 큐가 full 이 된지 알려면 무조건 이 큐의 현재 무게를 담는 sum이 필요하다고 생각은했지만 제일 앞에 있는 큐가 어디에 위치하고 있는지 알려면 ll.size()가 필요 한데, 이는 offer(0) 없이는 이렇게 간단한코드로 불가능하기 때문이다.

좋은 웹페이지 즐겨찾기