프로그래머스 - 다리를 지나는 트럭

프로그래머스 - 다리를 지나는 트럭

---

카테고리: 스택/큐

레벨: 2

언어: Java

 

문제

---

 

입출력 예시

---

 

풀이

---

이번 문제도 이해하는데 어렵지 않다. 그림으로 먼저 이해를 해보자.

예제 1번을 생각하면서 그림을 그려보면 위의 그림과 같이 트럭들이 대기하고 있는 상태이다.

다리는 총 10의 무게를 견딜 수가 있으므로 각 트럭의 무게를 고려하며 지나가야 된다.

여기서 다리의 길이는 2이다. 즉, 트럭이 다리를 지나갈 때 최대 2대만 지나갈 수 있다.

먼저 무게가 7인 트럭이 다리를 건너고 있다면 다리가 견딜 수 있는 무게를 생각해 나머지 트럭들이 대기한다.

 

무게가 7인 트럭이 지나가고 나서 대기하고 있던 무게가 4인 트럭이 다리를 지나가게 된다.

 

다리가 견딜 수 있는 무게는 총 10이므로 무게가 4인 트럭과 5인 트럭이 함께 지나가도 문제 되지 않는다.

 

무게가 4인 트럭이 다리를 지나가고 무게가 5인 트럭이 다리를 지나고 있는데 다리가 견딜 수 있는 무게를 넘기면 안 되기 때문에 무게가 6인 트럭은 대기한다.

 

무게가 5인 트럭이 지나가고 마지막으로 남은 무게가 6인 트럭이 다리를 지나면 프로그램이 종료된다.

 

그림을 보면 알 수 있지만 이 문제의 핵심은 트럭의 무게와 다리의 무게 그리고 다리의 길이가 중요하다.

public static int solution(int bridge_length, int weight, int[] truck_weights) {
    Queue<Integer> queue = new LinkedList<>();
    int sum = 0;
    int count = 0;      // 트럭이 다리를 지나간 시간

    for (int time : truck_weights) {        // 현재 트럭은 4대
        while (true) {
            if (queue.isEmpty()) {
                queue.add(time);
                sum += time;                // 처음 트럭이 다리를 건널 때(무게 7인 트럭)
                count++;                    // 시간 + 1
                break;
            } else if (queue.size() == bridge_length) {     // 현재 다리에 있는 트럭이 총 다리의 길이와 같을 때
                sum -= queue.poll();        // 다리에서 트럭을 하나 빼주기
            } else {
                if (sum + time > weight) {      // 다리를 건너고 있는 트럭과 다음 건너는 순서인 트럭의 무게를 합쳤을 때 다리가 견딜 수 있는 무게보다 클 경우
                    queue.add(0);               // 다리에 트럭을 올리지 않고 그냥 0을 추가
                    count++;                    // 시간 + 1
                } else {
                    queue.add(time);            // 다리를 건너고 있는 트럭과 다음 건너는 순서인 트럭의 무게를 합쳤을 때 다리가 견딜 수 있는 무게보다 작을 경우
                    sum += time;                // 현재 다리를 건너고 있는 트럭의 무게에 새로 다리를 건너는 트럭의 무게를 더하기
                    count++;                    // 시간 + 1
                    break;
                }
            }
        }
    }
    return count + bridge_length;           // 마지막으로 다리를 건너는 트럭은 다리의 길이 만큼 시간이 걸리기 때문에 더해준다.
}

이제 정답 코드를 살펴보자.

먼저 다리의 역할을 해줄 Queue를 하나 선언해준다. 그리고 count 변수를 만들어 트럭이 지나는 시간을 체크해 준다.

처음에는 다리에 트럭이 없기 때문에 대기하고 있는 트럭 중 맨 앞에 있는 트럭이 지나가게 된다. 그 후 대기하고 있는 트럭의 무게와 다리가 견딜 수 있는 무게를 비교하여 트럭을 옮겨준다.

이때 중요한 점은 두 개의 트럭 무게의 합이 다리가 견딜 수 있는 무게보다 클 경우 queue에는 0을 삽입해줘야 한다.

0을 삽입하여 queue에 있는 트럭을 지나가게 만들어 준다.

마지막 트럭이 다리를 지나갈 때는 다음으로 오는 트럭이 없기 때문에 최종 시간에 마지막 트럭이 지나가는 다리의 길이만큼 더하여 출력해 준다.