[백준/Java] 11003 : 최솟값 찾기

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

 

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

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

 

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

public class Backjoon_11003_최솟값_찾기 {
    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();
    }
}