[BOJ/Java] 13335 트럭

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ13335 {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine());
		// 트럭 개수 n
		int n = Integer.parseInt(st.nextToken());
		// 최대 대수 w
		int w = Integer.parseInt(st.nextToken());
		// 최대 하중 limit
		int limit = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(in.readLine());

		// queue 2개로 해결해보자 (다른 풀이 참고 했음)
		// 하나는 truck, 하나는 bridge;
		Queue<Integer> bridge = new LinkedList<>(), truckQ = new LinkedList<>();

		for (int i = 0; i < n; i++) {
			truckQ.offer(Integer.parseInt(st.nextToken())); // 7 4 3 2 5
		}
		in.close();
		for (int i = 0; i < w; i++) {
			bridge.offer(0); // 0 0
		}

		int count = 0, currentL = 0, tr;
		// bridge가 빌 때까지
		while (!bridge.isEmpty()) {
			while (!truckQ.isEmpty()) {
				tr = truckQ.peek();
				currentL += tr - bridge.poll();
				if (currentL > limit) {
					bridge.offer(0);
					currentL -= tr;
				} else {
					bridge.offer(tr);
					truckQ.poll();
				}
				count++;
			}
			count++;
			bridge.poll();
		}
		System.out.println(count);
	}
}

queue의 사용법에 대해서 아아주 제대로 익혀볼 수 있던 문제였다. 2시간이 넘도록 결국 접근조차 제대로 못하고 다른 풀이를 보고 힌트를 얻어서 다시 짜봤다. 진짜 알고리즘 바보인가. 컴띵이 좀 된다고 착각했던 지난 날의 나 반성해...

 

truck들 queue와 bridge queue 2가지 queue를 사용하는 방법. bridge queue에 0 등의 값을 넣고 사용하는 생각. 이걸 과연 스스로 할 수 있을까?

 

사실 접근 개념 자체는 정말 간단한 생각이었다. 하지만 머리 속에 있는 알고리즘을 실제로 구현해내는 것은 너무나 어렵다.

처음에는 다른 문제에서 했던 것처럼 index를 가지고 있는 객체를 queue에 넣고 그 index를 변화시키려고 생각하고 접근했다. 하지만 이런 접근법 자체가 queue에 대한 이해력이 떨어진다는 것을 방증한다고 생각된다... queue에 넣고 중간에 있는 요소에 접근할 방법이 없는데, 무슨 array 마냥 착각을 했다.

 

접근하는 방법 자체가 정말 중요하구나. 자료 구조 사용법에 대한 이해도를 높이자.