최솟값 찾기

백준 11003번 최솟값 찾기

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

예제 입력 1	예제 출력 1
12 3	1 1 1 2 2 2 2 2 3 3 2 2
1 5 2 3 6 2 3 7 3 5 2 6

풀이

슬라이딩 윈도우를 덱으로 구현하여 정렬 효과 이용.
덱은 양 끝에서 데이터를 삽입하거나 삭제할 수 있다.

덱에서는 (인덱스, 숫자) 형태의 노드를 구현한다.

위 예제에서 (1, 1) (2, 5)가 덱에 저장되어 있고 새 노드 (3, 2)가 덱에 저장되는 경우를 살펴보자.
뒤에서부터 비교를 시작하여 숫자가 작으면 덱에서 제거한다. (2, 5) 노드는 (3, 2) 노드보다 숫자가 크므로 덱에서 제거한다. (1, 1)은 (3, 2)보다 작으므로 탐색을 멈추고 노드를 저장하여 덱에는 (1, 1) (3, 2)가 있다. 최솟값은 첫번째에 있는 (1, 1)이다.
다음으로 (4, 3) 노드를 추가하는 경우 (1, 1) 노드가 슬라이딩 윈도우의 범위를 벗어나기 때문에 삭제한다. 4(마지막 노드 인덱스) - 3(슬라이딩 윈도우 크기) >= 1 노드 (4, 3)은 (3, 2)보다 숫자가 크므로 덱에는 (3, 2) (4, 3) 남아있고 최솟값은 2이다.

이러한 형태로 덱에 노드를 계속 저장하며 맨 앞에 있는 노드의 숫자를 출력하면 된다.

소스

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

class Node {
	int index;
	int value;
	
	Node(int index, int value) {
		this.index = index;
		this.value = value;
	}
}

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		final int N = Integer.parseInt(st.nextToken()); // 데이터 개수
		final int L = Integer.parseInt(st.nextToken()); // 최솟값 구하는 범위
		Deque<Node> deque = new LinkedList<>();
		st = new StringTokenizer(br.readLine());
		
		for(int i = 1; i <= N; i++) {
			int value = Integer.parseInt(st.nextToken()); //데이터 하나 읽어오기

			while(!deque.isEmpty() && (deque.getLast()).value > value)
				deque.removeLast();
			deque.addLast(new Node(i, value));
			
			while((deque.getFirst()).index <= i - L)
				deque.removeFirst();
			bw.write((deque.getFirst()).value + " ");
		}
		bw.flush();
		bw.close();
	}
}