알고리즘/자료구조

[백준] 11003 최솟값 찾기 (슬라이딩 윈도우, 덱) - Java

jny0 2023. 5. 14. 17:33

 

 

11003번: 최솟값 찾기

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

www.acmicpc.net

 

문제 상황

 

접근법

일정한 범위 안에서 최솟값 찾기

  • 슬라이딩 윈도우와 정렬을 사용해야함
  • 일반적인 정렬을 사용하면 시간초과가 나기 때문에 슬라이딩 윈도우를 덱으로 구현하면 정렬 효과를 볼 수 있음
  • 덱에 새 값이 저장될 때 덱의 가장 뒤의 값이 저장하려는 값보다 크면 제거함
  • 제거가 끝난 후 최솟값을 출력

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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 M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        Deque<Integer> dq = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();

        st =  new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < M; i++) {
            while(!dq.isEmpty() && dq.peekLast() > arr[i]){
                dq.pollLast();
            }
            dq.addLast(arr[i]);
            sb.append(dq.peekFirst()).append(" ");
        }

        for (int i = M; i < N; i++) {
            if (dq.peekFirst() == arr[i-M]) {
                dq.pollFirst();
            }
            while(!dq.isEmpty() && dq.peekLast() > arr[i]){
                dq.pollLast();
            }
            dq.addLast(arr[i]);
            sb.append(dq.peekFirst()).append(" ");
        }

        System.out.println(sb.toString().trim());
    }
}