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()로 꼬리값을 제거한다.
- a.
- (4) DECK의 front를 확인하여, 이미 구간 내의 값이 아니면 삭제한다.
(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;
}
}
