[백준(Baekjoon)][자바(java)] 11003 : 최솟값 찾기 / 슬라이딩 윈도우, 덱

 

www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

 

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.
D_i = A_(i-L+1) ~ A_i 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)
둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

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

예제 입력 1

12 3
1 5 2 3 6 2 3 7 3 5 2 6

예제 출력 1

1 1 1 2 2 2 2 2 3 3 2 2

 

문제 풀이

 

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

public class Main {
	
	public 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() ), 
		    l = Integer.parseInt( st.nextToken() );
		int a[] = new int[n], i;
		st = new StringTokenizer( br.readLine() );
		for( i = 0; i < n; i++ )
			a[i] = Integer.parseInt( st.nextToken() );
		br.close();
		
		Deque<int[]> dq = new LinkedList<>();
		int d[] = new int[n];
		for( i = 0; i < n; i++ ) {
			while( !dq.isEmpty() && dq.getFirst()[1] <= i-l )
				dq.pollFirst();
			while( !dq.isEmpty() && dq.getLast()[0] > a[i] )
				dq.pollLast();
			dq.add( new int[] { a[i], i } );
			d[i] = dq.peekFirst()[0];
		}
		
		StringBuilder sb = new StringBuilder();
		for( int dd : d )
			sb.append( dd + " " );
		
		System.out.println( sb.toString() );
	}
}

 

*  덱, 슬라이딩 윈도우

-  i-L+1 ~ i 번째의 수들 중 가장 작은 값을 담을 d[] 배열 생성
-  { a[i], i } ( { val, idx } )가 담긴 int[] 배열을 담아 최솟값을 구할 Deque<int[]> 생성
-  a[] 순회하면서 이 두 조건에 맞도록 Deque안의 요소들을 적절히 뺀 후 { a[i], i }를 넣는다
 ┌ Deque에 담긴 첫 번째 요소의 idx( dq.getFirst()[1] )가 i-L 보다 크거나 같아야 함
 └ Deque에 담긴 마지막 요소의 val( dq.getLast()[0] )가 a[i]보다 작거나 같아야 함
-  i-L+1 ~ i 번째에서의 가장 작은 수( d[i] )는 dq.peekFirst()[0]가 된다