[백준] 13335 : 트럭 - JAVA

한 번에 맞았지만, 테스트케이스에서 결과가 달라서 조금 헤매기도했고, 처음에는 Queue를 이용해서 풀려고했는데 트럭이 얼마나 이동했는지를 큐 안에서 어떻게 표현할까를 고민하다가 배열 2개 사용하는 방식으로 바꾸었다.

그래서 다른 풀이를 찾아보고 공부한다.

내 풀이

import java.util.*;
import java.io.*;

public class Main {
	static int[] weight;
	static int[] moveCnt;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		weight = new int[n];
		moveCnt = new int[n];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			weight[i] = Integer.parseInt(st.nextToken());
		}
		
		int startIdx = 0, endIdx = 0;
		int sum = weight[0];
		moveCnt[0] = 1;
		int totalTime = 1;
		while(endIdx < n) {
			totalTime++;
			for(int i=startIdx; i<=endIdx; i++) {
				if(++moveCnt[i] > w) {
					startIdx = i+1;
					sum -= weight[i];
				}
			}
			if(startIdx >=n) break;
			if(startIdx > endIdx)  {
				endIdx = startIdx;
			}
			if(endIdx >= n) break;
			// 새로운 트럭 유입 
			if(moveCnt[endIdx] == 0) {
				if(sum + weight[endIdx] <= L) {
					moveCnt[endIdx]++;
					sum += weight[endIdx];
				}
			} else if(endIdx +1 <n) {
				if(sum + weight[endIdx+1] <= L) {
					endIdx++;
					moveCnt[endIdx]++;
					sum += weight[endIdx];
				}
			}
		}
		totalTime += (w-moveCnt[endIdx]+1);
		System.out.print(totalTime);
	}
}

다른 풀이

import java.util.*;
import java.io.*;

public class Main {
	static Queue<Integer> truck = new LinkedList<>();
	static Queue<Integer> bridge = new LinkedList<>(); 

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			truck.offer(Integer.parseInt(st.nextToken()));
		}
		
		for(int i=0; i<w; i++) {
			bridge.offer(0); // w만큼 0의무게인 트럭을 넣어 두기
		}
		
		int sumWeight = 0;
		int totalTime = 0;
		while(!bridge.isEmpty()) {
			totalTime++;
			sumWeight -= bridge.poll();
			
			if(!truck.isEmpty()) {
				if(sumWeight + truck.peek() <= L) {
					sumWeight += truck.peek();
					bridge.add(truck.poll());
				} else {
					bridge.add(0);
				}
			}
		}
		System.out.print(totalTime);
	}
}

Queue를 2개 이용해서 구현했다.

배열을 이용했을 때와 비교해서 메모리나 시간면에서 크게 차이가 없지만, 선입선출의 특징을 이용하므로 예외 처리 할 부분이 덜해서 코드가 훨씬 간결하다.

배울 점

• 트럭의 이동정도는 무게가 0인 트럭이 있다고 가정해서, 큐에 0을 넣어 해결했다.