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

 

11003번: 최솟값 찾기

 

문제 상황

 

접근법

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

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

 

 

문제 풀이

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());
    }
}