백준 11003번 자바 ☆

문제

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

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 Main11003 {

	static int N,L;
	static Deque<Node> dq;
	
	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());
		
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		dq = new LinkedList<Node>();
	
		for (int i=0; i<N; i++) {
			int temp = Integer.parseInt(st.nextToken());
			
			while (!dq.isEmpty() && dq.getLast().val > temp) {
				dq.removeLast();
			}
			
			dq.addLast(new Node(temp, i));
			
			if (dq.getFirst().idx <= i - L) {
				dq.removeFirst();
			}
			
			bw.write(dq.getFirst().val + " ");
		}
		
		bw.flush();
		bw.close();
	}
	
	static class Node {
		private int val;
		private int idx;
		
		public Node(int val, int idx) {
			this.val = val;
			this.idx = idx;
		}
	}
}

1. 덱이라는 자료구조를 이용하면 어렵지 않게 풀 수있다. 덱을 몰라 List로만 하려다보니 계속 애를 먹었다.

 

2. 덱의 마지막 부터 탐색을 할 때, 새로들어올 숫자가 기존에 있는 숫자보다 작을 경우 마지막 인덱스의 아이템을 삭제한다. 

 

그 다음 덱이 가지고 있는 아이템들의 인덱스 범위가 L을 초과할 경우 덱의 첫번째 아이템을 제거한다.

 

3. 그 다음 출력해주면 끝.

 

정리 : 덕분에 Deque라는 자료구조 하나 공부했다.