프로그래머스_스택/큐_다리를 지나는 트럭 (JAVA)

문제 설명 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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 이하입니다. 입출력 예

 

 

큐 구조를 이용하는 간단한 문제입니다. 주의할 점은 입출력 예를 보면서 정확히 문제를 파악해야한다는 점입니다. 트럭 한대가 길이가 2인 다리를 지나는 것은 2초가 아니라 3초가 걸리는 것으로 설정돼 있습니다. 

 

---

 

다리 위에 첫 번째 트럭이 발을 딛는 순간부터 마지막 트럭이 나가는 순간까지의 시간경과이므로 반복문이 한 번 도는 것을 1초 단위로 생각하면 편하게 풀 수 있습니다. 다리를 큐로 보고 트럭을 한대씩 넣어줬다가 가진 시간이 다 지나 0이 되면 빼주면 됩니다. 

 

package pojoPrj;

import java.util.LinkedList;
import java.util.List;

class Solution {

	public int solution(int bridge_length, int weight, int[] truck_weights) {

		// int[] : 트럭 무게, 다리를 지나간 시간
		List<int[]> queue = new LinkedList<int[]>();
		int answer = 0;

		int i = 0;
		int totalWeight = 0;
		while (true) {

			// 다리위에 올라가 있는 트럭이 있다면 시간 1씩 감소 (0 이하면 삭제)
			for (int j = 0; j < queue.size();) {

				if (--queue.get(j)[1] == 0) {
					totalWeight -= queue.get(j)[0];
					queue.remove(j);
				} else {
					j++;
				}
			}

			// "현재 차례의 트럭 무게 + 다리위에 놓인 총 트럭 무게"가 weight 보다 작다면 다리에 올라감
			if (i < truck_weights.length && truck_weights[i] + totalWeight <= weight) {
				totalWeight += truck_weights[i];
				queue.add(new int[] { truck_weights[i++], bridge_length });
			}

			// 1초 증가
			answer += 1;

			// 다리에 트럭이 더이상 없으면 종료
			if (queue.size() == 0) {
				break;
			}

		}

		return answer;
	}
}