1. 슬라이딩 단조 큐란 무엇인가요?

슬라이딩 단조 큐란, DECK을 활용해 구현한 슬라이딩 윈도우로, 슬라이딩 윈도우 구간 내의 최소값, 최대값을 O(1)에 찾기 위해 고안한 구현체이다. 단조라는 이름이 붙은 이유는, 구간 내 최소값을 찾고 싶을 경우, Deck 내부 원소들이 오름차순으로 유지되고, 구간 내 최대값이 찾고 싶은 경우 내림차순으로 유지되기 때문이다.

사실 내가 만든 이름이다...😂

슬라이딩 윈도우 심화 문제를 풀면서, 슬라이딩 윈도우를 Deck으로 구현한 형태가 꾸준히 나오는데, 인터넷 여기 저기 찾아봐도, 형태만 있을 뿐 이것의 제대로 된 이름이 없었다.

따라서 정식 명칭은 아니지만! 설명의 편의를 위해 앞으로 현 구간 내의 최소값과 최대값을 찾기 위해 Deck으로 구현한 슬라이딩 윈도우를 슬라이딩 단조 큐 (Sliding Mono Queue)라고 부르겠다.

2. 왜 쓰나요?

위에서 용도를 설명했지만, 윈도우 구간 내의 최소값이나 최대값을 O(1)에 구하기 위해서 사용한다.

(1) 기본 슬라이딩 윈도우로는 구간 내 최소 혹은 최대값을 찾을 수 없나요?

기본 슬라이딩 윈도우로 최소값 혹은 최대값을 찾는다면, 슬라이딩 윈도우를 쓰는 의미가 없다.

우리가 슬라이딩 윈도우 스킬을 썼던 이유는 매 움직임마다 완전 탐색으로 계산해야 했던, 특정 구간의 구성요소 개수나 합을, 맨 왼쪽 빠지는 값과 오른쪽 값 두 개만 신경쓰면 되도록 시간 복잡도를 줄여줬기 때문이다.

하지만 최소, 최대값의 경우 어떤가. 빠지는 값이 몇 번째로 작은 수인지 모르고, 들어오는 값이 몇 번째로 큰 값인지 단번에 파악이 어렵다. 이렇게 되면, 삽입값과 삭제값에 따른 순위 변동을 매 움직임마다 계산해야해서, 슬라이딩 윈도우 사용의 이유를 잃는다.

3. 어떻게 사용하나요?

다음 과정을 따르면 된다. 우리는 구간 내 최소값을 DECK의 PEEK()으로 유지하는 것을 목표로 하겠다. 이제 DECK 안은 무조건 오름차순이 유지되어야 한다.

(0) 삽입될 값들은 객체 형태로 배열에서의 index와 value를 가지고 있어야 한다.
(1) DECK을 만든다.
(2) DECK이 비어있으면, 삽입 값을 무조건 넣는다.
(3) DECK이 비어있지 않으면,
- a. DECK.peekLast()의 가치 <= 삽입값의 가치이면 삽입값을 DECK 꼬리에 삽입한다.
- b. DECK.peekLast()의 가치 > 삽입값의 가치: (3)-a가 성립할 때까지 DECK.pollLast()로 꼬리값을 제거한다.
(4) DECK의 front를 확인하여, 이미 구간 내의 값이 아니면 삭제한다.

따라서 1을 삭제. 이제 잘 보면 단조 큐의 peek()이 해당 구간의 최소값임을 볼 수 있음.

(1) `DECK.peek()`의 의미

위의 방식대로 가면 DECK의 peek은 무조건 최소값이 유지될 것이다. 해당 최소값은 현 구간 내의 최소값을 의미한다.

(2) 오름차순 유지 이유

구간이 움직이면서, 만약 deck의 peek이 구간에 더 이상 속하지 아니하게 되어 빠져 나간다면? 그 다음 작은 값이 최소값이 되어야 한다. 이를 위해서 deck 내부를 오름 차순으로 유지하는 것이다. deck 안의 원소들은 최소값 후보들이다.

(3) 3번 해석

우리는 구간 내 최소값을 유지 해야한다.

(a) 삽입값이 Deck.peekLast() 보다 크거나 같다면, 당장은 최소값이 될 수 없지만, 윈도우가 움직임에 따라 추후에 최소값이 될 수도 있다. 따라서 살려두고 DECK의 꼬리칸에 탑승 시킨다.

(b) 삽입값이 Deck.peekLast()보다 작다면, Deck.peekLast()에 있는 값은 더 이상 쓸모가 없어진다. 왜냐하면, 신규로 들어오는 값이 최소라면, Deck.peekLast()은 그것이 구간에서 빠져 나가는 그 날까지 영원히 최소값이 될 수 없기 때문이다. 따라서 헛된 희망은 가지지 않게 미리 삭제 해준다.

4. 코드

import java.io.*;
import java.util.ArrayDeque;


public class Main {
    public static void main(String[] args) throws IOException {
        int [] arr = new int[]{1, 5, 2, 3, 6, 2, 3, 7, 3, 5, 2, 6};
        slidingMonoQueue(arr, 3);
    }

    public static void slidingMonoQueue (int [] arr, int W) { // arr = 전체 배열, W = 윈도우 크기
        ArrayDeque<Num> window = new ArrayDeque<>();

        for (int i = 0; i < arr.length; i++) {
            if(window.isEmpty()) window.add(new Num(i, arr[i]));
            else {
                while (!window.isEmpty() && window.peekLast().v > arr[i]) window.pollLast();
                window.add(new Num(i, arr[i]));
            }
            if(!window.isEmpty() && window.peek().i <= i-W) window.poll();

           if(!window.isEmpty()){
               System.out.printf("현재 영역: %d ~ %d의 최소값: %d\n", i-W+1, i, window.peek().v);
           }
        }
    }
}

class Num {
    int i;
    int v;

    public Num (int i, int v){
        this.i = i;
        this.v = v;
    }
}