[KOITP] Sliding Windows

출    처 : http://koitp.org/problem/SLIDING_WINDOWS/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
3.0 초	512 MB	825	97 (12%)	76

문제

길이가 N인 정수 배열이 있다. 이 배열의 부분배열 중 크기가 K인 부분배열은 총 N-K+1개 있다. 이 부분배열에 대해 부분배열에 속한 최대값, 최소값, 합을 구하는 프로그램을 작성하자.

예를 들어, 배열 [1, 3, -1, -3, 5, 3, 6, 7]이 있고 K=3이라 하자. 이 배열에 크기가 3인 6개의 부분배열들이 있고, 왼쪽에 있는 부분배열부터 순서대로 나열하면 다음과 같다: [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6], [3, 6, 7]. 각 부분배열의 최소값은 순서대로 -1, -1, -3, -3, 3, 3이고, 최대값은 순서대로 3, 3, 5, 5, 6, 7이며, 부분배열의 합은 순서대로 3, -1, 1, 5, 14, 16이다.

입력

첫 줄에 배열의 크기 N과 부분배열의 크기 K가 주어진다. (1 ≤ K ≤ N ≤ 1,000,000)

둘째 줄에 배열의 내용을 나타내는 N개의 정수들이 공백으로 구분되어 주어진다. 주어지는 수는 절대값이 1,000,000,000 보다 크지 않다.

출력

출력은 총 N-K+1개의 줄로 구성되며 각 줄에 부분배열의 최소값, 최대값, 합이 공백으로 구분되어 출력한다. 출력은 왼쪽에 위치한 부분배열에 대한 값들부터 차례대로 출력한다.

힌트

예제 입력

8 3
1 3 -1 -3 5 3 6 7

예제 출력

-1 3 3
-3 3 -1
-3 5 1
-3 5 5
3 6 14
3 7 16

< Comment >

 Deque 를 이용하여 문제를 풀었는데, 생각보다 발상 자체는 단순한데, 막상 안 쓰던 자료구조를 쓰려니 헷갈리기도 해서 소스코드가 뭔가 지져분해졌습다. 기본 아이디어는 심플하게 현재 입력받은 값보다 큰 값이 자신보다 앞쪽에 들어가 있으면, 이 경우에는 뒤에서부터 차례대로 빼주고 자신을 더해줍니다. 결국 항상 최대값이 맨 앞에 남아있을 것이고, 이 점을 이용하여 문제를 풀었습니다. 최소값의 경우도 마찬가지이고, 다만 주어진 K의 크기를 넘어서게 되면, 이 경우에는 범위를 넘어서므로, 맨 앞쪽에 있는 최대값이 혹여 범위를 벗어나는 경우에는 제거를 해 주는 식으로, 진행했습니다.

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

public class SlidingWindows {
	
	public static int N = 0;
	public static int K = 0;
	
	public static int arr[] = null;
	public static long min[] = null;
	public static long max[] = null;
	public static long sum[] = null;
	
	public static void main(String[] args) throws Exception {
		
		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());
		K = Integer.parseInt(st.nextToken());
		
		arr = new int[N+1];
		min = new long[N+1];
		max = new long[N+1];
		sum = new long[N+1];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 1 ; i <= N ; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Deque<Integer> dq = new ArrayDeque<>();
		Deque<Integer> IdxDq = new ArrayDeque<>();
		
		for (int i = 1 ; i <= N ; i++) {
			
			while(!dq.isEmpty()) {
				if (dq.peekLast() < arr[i]) {
					dq.pollLast();
					IdxDq.pollLast();
				} else {
					break;
				}
			}
			
			dq.addLast(arr[i]);
			IdxDq.addLast(i);
			
			while (IdxDq.peekLast() - IdxDq.peekFirst() >= K) {
				dq.pollFirst();
				IdxDq.pollFirst();
			}
			
			max[i] = dq.peekFirst();
		}
		
		while(!dq.isEmpty()) {
			dq.pollLast();
		}
		
		while(!IdxDq.isEmpty()) {
			IdxDq.pollLast();
		}
		
		for (int i = 1 ; i <= N ; i++) {
			
			while(!dq.isEmpty()) {
				if (dq.peekLast() > arr[i]) {
					dq.pollLast();
					IdxDq.pollLast();
				} else {
					break;
				}
			}
			
			dq.addLast(arr[i]);
			IdxDq.addLast(i);
			
			while (IdxDq.peekLast() - IdxDq.peekFirst() >= K) {
				dq.pollFirst();
				IdxDq.pollFirst();
			}
			
			min[i] = dq.peekFirst();
		}
		
		
		for (int i = 1 ; i <= N ; i++) {
			sum[i] = sum[i-1] + arr[i];
		}
		
		for (int i = K ; i <= N ; i++) {
			bw.write("" + min[i] + " " +  max[i] + " " + (sum[i] - sum[i - K]) + "\n");
		}
		bw.flush();
		bw.close();
		
	}
}