백준 JAVA11 11003번 : 최솟값 찾기

최솟값 찾기

백준 11003번 상세보기

문제

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

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

Flow.

• ex) N= 12, L = 3
• i = 12
• 최솟값을 구해야하는 범위 → 12 - 3 + 1 ~ 12 → 10 ~ 12 이므로 범위는 3이다.
• ex) 1 - 3 + 1 ~ 1의 경우 → -1 ~ 1 까지 구함으로 최솟값은 1
• 즉 L = 윈도우
• 정렬로 풀면 쉽겠지만 N의 범위는 5,000,000 이므로 사용할 수 없다.
• Deque(정렬 기능으로 구현) 와 Node 사용 Node(index, value)

package slidingWindow;

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;

public class P11003_minValue {

	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());

		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());

		Deque<Node> deque = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			int now = Integer.parseInt(st.nextToken());
			//덱의 마지막 값이 현재 들어온 값보다 크다면 제거한다.
			while (!deque.isEmpty() && deque.getLast().value > now) {
				deque.removeLast();
			}
			//아니라면, 해당값을 노드 객체로 덱에 넣어준다. 
			deque.addLast(new Node(now, i));
			//문제의 범위 값 설정 i - L + 1
			if (deque.getFirst().index <= i - L) {
				deque.removeFirst();
			}
			bw.write(deque.getFirst().value + " ");
		}
		bw.flush();
		bw.close();

	}

}

class Node {
	public int value;
	public int index;

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