[프로그래머스] 42583번 : 다리를 지나는 트럭

코드

import java.util.LinkedList;
import java.util.Queue;

public class PRO_42583 {
    public static int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> queue = new LinkedList<>();
        int sum = 0;
        int time = 0;

        for (int i = 0; i < truck_weights.length; i++) {
            int truck = truck_weights[i];

            while (true) {
                if (queue.isEmpty()) {
                    queue.add(truck);
                    sum += truck;
                    ++time;
                    break;
                } else if (queue.size() == bridge_length) {
                    sum -= queue.poll();
                } else {
                    if (sum + truck <= weight) {
                        queue.add(truck);
                        sum += truck;
                        ++time;
                        break;
                    } else {
                        queue.add(0);
                        ++time;
                    }
                }
            }
        }
        return time + bridge_length;
    }

    public static void main(String[] args) {
        int bridge_length = 2;
        int weight = 10;
        int[] truck_weights = {7, 4, 5, 6};

        System.out.println(solution(bridge_length, weight, truck_weights));
    }
}

풀이 및 느낀점

큐를 이용하여 문제에 접근했다.

다리에 트럭을 넣는 조건은 총 3가지이다.

1. 큐가 비어있는 경우
2. 큐가 가득 차지 않은 경우
3. 큐가 가득 찬 경우

큐가 비어있는 경우에는 트럭을 넣어주고 트럭의 무게를 저장할 sum 값에 올라간 트럭의 무게를 더해준다. 그리고 시간은 1 증가시켜준다.

큐가 가득 차지 않은 경우에는 또 두가지의 경우가 나뉜다. 트럭을 추가했을때 다리의 길이를 초과하는 경우와 그렇지 않는 경우이다. 초과한다면, 0을 추가해주고 시간을 1 증가시킨다. 초과하지 않는다면, 추가한 트럭 무게를 sum에 더해주고 시간을 1 증가시킨다.

큐가 가득 찬 경우는 맨 앞에 있는 트럭을 제거해주고 sum에서 앞 트럭의 무게를 빼준다.

정답을 출력할 때 time에 다리 길이를 더해준 이유는 마지막 트럭이 다리를 모두 건너는 시간까지 추가해야하기 때문이다. for문에서 마지막 트럭이 올라가는 경우만 고려했기 때문에 리턴할 시에는 건너는 상황까지 고려해야한다.

참고자료