백준 11003번(최솟값 찾기)[JAVA]

풀이

주어진 범위 안에서 최솟값을 찾는 문제이다. 주어진 범위가 움직이므로, 윈도우 슬라이딩 문제이다. 윈도우 슬라이딩이란, 범위가 창문 움직이듯이 옆으로 옮겨가는 것이다. 이 문제의 경우, n은 5,000,000이고, l은 10^9이다…즉, O(n)인 알고리즘으로만 풀어야 한다. 그렇다면, 정렬의 시간 복잡도 하한선이 O(nlogn)이므로, 어떠한 정렬도 사용하지 못한다.
즉, 각각의 범위에서 1번의 비교로 n개의 최솟값을 찾아야한다. 또한, 숫자를 입력받는 즉시, 기존의 최솟값과 비교하면서 최솟값을 도출해야 시간복잡도가 O(n)이 된다.

배열에 저장하고 꺼내서 비교하니까 시간 초과가 뜬다…

그렇기 때문에, 이 문제는 class를 활용한 deque를 사용하여 풀어야한다. for문을 통해 n번 반복하면서, 일단 입력받은 수를 저장(addLast())한다. addLast()를 했기 때문에, 덱의 뒤쪽에서부터 값이 저장된다. 덱에서의 알고리즘은 아래와 같다.

• 덱이 비어있을 경우, addLast()한다.
• for문의 i에 따라서 window가 움직인다. 윈도우의 범위는 이 문제에서 i-l이다. 맨 왼쪽에 있는 값의 인덱스가 이 범위를 벗어났을 때, 맨 왼쪽에 있는 값을 제거(removeFirst())한다.
• 덱에 보관하고 있는 수의 맨 오른쪽 수를 다음 입력받은 수와 비교하여, 보관하고 있는 숫자가 입력받은 수보다 크면, 그 값을 제거(removeFirst())하고 입력받은 수는 저장한다.
• 그게 아닌 경우, 그냥 저장(addLast())한다. 위와 같은 알고리즘을 거치면, for문이 한번 돌 때마다(각 윈도우 범위에서마다) 맨 왼쪽에 있는 노드가 최솟값이다. 이 값들을 출력해주면 정답인 것이다…!

  • 배열에 저장해놓고 출력했더니 시간 초과이다…BufferedWriter를 사용하여 한번에 출력해야 한다… 알고리즘 자체보다, 시간복잡도 맞추는게 더 힘들었다.
    
  • 시간 복잡도 맞추는게 까다롭다? Scanner는 당연히 안된..다..

소스 코드

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

public class 최솟값찾기 {
	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 l = Integer.parseInt(st.nextToken());
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		st = new StringTokenizer(br.readLine());
		
		Deque<Node> state = new LinkedList<>();
		
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
			
			while (!state.isEmpty() && state.getLast().value > num) {
				state.removeLast();
			}
			
			state.addLast(new Node(num, i));
			
			if (state.getFirst().index <= i-l) {
				state.removeFirst();
			}

			bw.write(state.getFirst().value + " ");
		}
		
		bw.flush();
		bw.close();
	}
	
	static class Node {
		public int value;
		public int index;
		
		Node(int value, int index) {
			this.value = value;
			this.index = index;
		}
	}
}

태클 감사합니다.
조언 환영입니다.