[백준] 11003. 최솟값 찾기 (Java)

 

🔒 문제

11003번: 최솟값 찾기

 

 

🔑 알고리즘

덱(Deque)

 

 

💡  풀이

새로운 값이 기존 값보다 더 작다면

그 기존 값들은 더 일찍 들어왔기 때문에 리스트에서 더 일찍 지워질 것이며

새로운 값이 더 작기 때문에 최소값에도 영향을 주지 못하는 필요없는 값이 된다.

 

따라서 새로운 값보다 작은 값이 나올 때까지 기존 값들을 지워주고

새로운 값을 추가해주면 자연스레 리스트의 맨 앞의 값이 해당 범위의 최소값이 된다.

 

문제의 예제 입력을 예로 들면 다음과 같다.

덱: [] ,       input: 1  -> [1]
덱: [1]  ,    input: 5  -> [1, 5]
덱: [1, 5]   input: 2  -> [1, 5, 2] -> [1, 2]
덱: [1, 2]   input: 3 ->  [1 ,2, 3] -> [2, 3]
덱: [2, 3]   input: 6 ->  [2, 3, 6] -> [2, 3, 6]
덱: [2, 3, 6]  input: 2 -> [2, 3, 6, 2] -> [2]

 

* 시간 제한이 빡빡해서인지 BufferedWriter를 사용하고, Integer[] 대신 클래스를 만들어야 시간 초과가 나지 않았다.

 

 

✏️ 코드

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

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));
		StringBuilder sb = new StringBuilder();

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());

		ArrayDeque<Node> deque = new ArrayDeque<>();

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());

			while (!deque.isEmpty() && deque.getLast().v > num)
				deque.removeLast();

			deque.add(new Node(num, i));

			if (i == deque.getFirst().i + L)
				deque.removeFirst();
			sb.append(deque.getFirst().v).append(" ");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static class Node {
		int v, i;

		public Node(int v, int i) {
			this.v = v;
			this.i = i;
		}

	}
}