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

문제설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.
예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예시

문제 풀이

다리를 건너는 트럭들은 동시에 이동한다는 점에서 자료구조 큐를 활용하여 문제를 풀어야겠다고 생각했다. 큐는 BFS문제를 풀 때도 활용되지만 이처럼 통과 같은 구조에 동시에 진행시켜야 할 땐 큐를 활용한다.
문제 해석이 조금 어려웠는데, 아무래도 트럭의 길이를 무의식 적으로 생각해서 그런 것 같다.
예시를 살펴보면 2초에 7kg트럭은 도착하기 일보직전이고, 다리에 완전히 오른 상태이다. 하지만 0.1초라도 지나면 다리에 완전히 오른상태가 아니게 되므로 다음 트럭이 출발 할 수 있는 것이다. 그렇게 대강 2초에 다음 트럭이 출발한다고 생각을 하고 쭉 이어 나갔다. 그렇게 마지막 트럭인 6kg트럭이 출발한 시점은 5.x초, 도착한 시점은 7.x초가 되기 때문에 최소 8초가 걸린다고 생각했다.
이러한 특성상 트럭의 길이를 그냥 1이라고 생각하거나 0초가 아닌 1초부터 시작한다고 생각하고 문제를 풀어야 마음이 편할 것 같다.

오류 발생 코드

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int tot_weight = 0;
        Queue<Integer> wait = new LinkedList<Integer>();
	    Queue<Node> cross = new LinkedList<Node>();
        for (int i = 0; i < truck_weights.length; i++) { // wait 큐에 트럭 삽입
			wait.offer(truck_weights[i]);
		}
		Node n;
		cross.offer(n = new Node(0, wait.poll())); // cross 큐에 첫 트럭 삽입
		tot_weight += n.weight;
		while (!cross.isEmpty()) {
			if (cross.peek().time == bridge_length) { // 다리를 다 지나면 큐에서 삭제
				tot_weight -= cross.poll().weight;
			}
			if (!wait.isEmpty() && tot_weight + wait.peek() <= weight) {// wait큐에 있는 트럭을 삽입해도 무게를 버틸 때
				Node m = new Node(0, wait.poll());
				cross.offer(m);
				tot_weight += m.weight;
			}
			for (Node i : cross) { // cross 큐에 있는 모든 요소 time++
				i.time++;
			}
			answer++;
		}
        return answer;
    }
}
class Node {
		int time, weight;

		Node(int time, int weight) {
			this.time = time;
			this.weight = weight;
		}
	}

3번 예시에서 시간 초과가 났다. 다른방법을 찾아봐야겠다.

프로그램 코드

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
		int tot_weight = 0;
		Queue<Node> wait = new LinkedList<Node>();
		Queue<Node> cross = new LinkedList<Node>();

		for (int i = 0; i < truck_weights.length; i++) { // wait 큐에 트럭 삽입
			wait.offer(new Node(truck_weights[i], 0));
		}

		while (!wait.isEmpty() || !cross.isEmpty()) {
			time++;
			if (!cross.isEmpty()) {
				Node t = cross.peek();
				if (time - t.time >= bridge_length) { // 다리를 다 지난 경우
					tot_weight -= t.weight;
					cross.poll();
				}
			}

			if (!wait.isEmpty()) {
				if (tot_weight + wait.peek().weight <= weight) {
					Node t = wait.poll();
					tot_weight += t.weight;

					cross.offer(new Node(t.weight, time));
				}
			}
		}
		return time;
	}

	static class Node {
		int time, weight;

		Node(int weight, int time) {
			this.time = time;
			this.weight = weight;
		}
	}
}

참고 코드