[백준/Java] 11003

최솟값 찾기

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

문제

N개의 수 $A_{1}, A_{2}, ..., A_{n}$과 L이 주어진다.

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

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 $A_{i}$가 주어진다. $(-10^9 ≤ A_{i} ≤ 10^9)$

출력

첫째 줄에 $D_{i}$를 공백으로 구분하여 순서대로 출력한다.

문제 풀이 방법 및 해설

이번 문제는 자료구조 문제이다. 이 문제를 해결하기 위해서 우선순위 큐도 사용해보았는데 우선순위 큐는 값을 추가 삭제 할 때마다 O(Log N) 시간복잡도가 발생해 시간초과가 발생할 수 있다.
그래서 데이터를 추가 삭제하는데 상수시간인 덱을 활용하였다.

실제 데이터를 관리하는 배열과 들어온 인덱스를 관리하는 Deque를 사용하였다. Deque에 값을 추가할 때마다 최근에 들어온 값과 비교해 최근에 들어온 값이 더 크다면 그 값을 삭제하고, 추가 후에는 처음에 들어온 값부터 인덱스를 검사해 유효 범위인지 확인을 한다.

풀이 코드

import java.io.*;
import java.util.*;
import java.util.LinkedList;

public class Main {
    public static 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());
        int L = Integer.parseInt(st.nextToken());

        Deque<Integer> pq = new ArrayDeque<>();
        int[] arr= new int[N+1];
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int idx = 1;
        st = new StringTokenizer(br.readLine());
        while(idx <= N){
            arr[idx] = Integer.parseInt(st.nextToken());
            while(!pq.isEmpty() && arr[pq.peekLast()] >= arr[idx]){
                pq.pollLast();
            }

            pq.offer(idx);
            int start = idx - L + 1 <= 0 ? 0 : idx - L + 1;

            while(pq.peek() < start){
                pq.pollFirst();
            }

            bw.write(arr[pq.peek()] + " ");
            idx++;
        }
        bw.flush();
        bw.close();
    }
}