[백준] 슬라이딩 윈도우 - 11003_최솟값 찾기 Java[자바]

 

이번 최솟값 찾기 문제는 DNA 비밀번호 문제와 비슷하지만 살짝 다른 문제이다.

 

DNA 비밀번호는 슬라이딩 윈도우 배열의 크기가 일정하게 유지가 되었다면 

 

이번 문제의 배열의 크기는 일정하게 유지되는 것이 아닌 변한다는 점이다.

 

여기서는 Deque를 사용하여 슬라이딩 윈도우 알고리즘을 사용할 것이다.

 

먼저 Deque는 Que 종류 중 하나로 Que의 양쪽으로 엘리먼트의 삽입과 삭제가 가능한 자료구조이다.

 

문제 해결 방법에 대해 말을 해보면

 

Deque에 현재 들어갈 값의 index와 value를 가진 객체를 넣어준다.

 

그 다음 들어갈 값의 value가 현재 들어가있는 마지막 값의 value보다 작으면

 

현재 들어가있는 마지막 값을 지우고 다음 들어갈 값을 Deque에 넣어준다.

 

여기서 최솟값을 조회하는 인덱스의 범위가 있으므로 

 

만약 처음 들어간 값의 index가 최솟값을 조회하는 index를 벗어나면 그 값을 Deque에서 제거한다.

 

그 후 맨 처음의 value를 StringBuilder에 추가해준뒤 최종 StringBuilder를 출력하면 답이 나온다.

 

아래 코드를 보자.

 

import java.io.*;
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());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Deque<Num> que = new LinkedList<>();
        for(int i = 0; i < N; i ++) {
            int now = Integer.parseInt(st.nextToken());
            
            while(!que.isEmpty() && now < que.getLast().value) {
                que.removeLast();
            }
            que.addLast(new Num(i, now));
            if(que.getFirst().index <= i - L) {
                que.removeFirst();
            }
            sb.append(que.getFirst().value + " ");
        }
        System.out.println(sb);
    }
    
    public static class Num {
        public int index;
        public int value;
        
        public Num(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }
}