안동민 개발노트

단조 스택/큐는 이름 때문에 어렵게 느껴질 수 있습니다. 하지만 실제로 하는 일은 단순합니다. 앞으로 절대 답이 되지 않을 후보를 지금 버린다가 전부입니다.

이 규칙을 쓰면 이중 루프 문제를 한 번 순회로 줄일 수 있습니다. 여기서는 코드 템플릿 암기보다 어떤 값을 버리고 어떤 값을 남길지를 우선 판단하는 연습을 합니다.

핵심 원리 해설

단조 패턴은 복잡한 공식을 외우는 기법이 아니라, 필요 없는 후보를 빨리 버리는 규칙입니다. 예제 배열을 하나 적고 각 인덱스가 push/pop 되는 순간을 직접 표시해 보세요.

단조 스택은 스택 안 값의 오름/내림 순서를 유지하는 구조입니다. 정확히는 새 원소를 넣기 전에 순서를 깨는 원소를 제거해서 정렬된 후보 집합을 유지합니다. 다음 큰 수 문제에서 작은 값이 스택 위에 있을 때 더 큰 값이 오면, 그 작은 값은 즉시 제거됩니다.

단조 큐는 슬라이딩 윈도우에서 유효한 극값 후보만 남기는 큐입니다. 큐 앞에 현재 구간의 최댓값(또는 최솟값)이 오도록 뒤쪽 열세 후보를 계속 삭제하며 유지합니다. 길이 k 윈도우 최댓값에서 새 값이 더 크면 뒤쪽 작은 값들은 이후 답이 될 수 없어 버립니다.

후보 제거(pruning)는 미래에 답이 될 수 없는 상태를 미리 지우는 과정입니다. 지배 관계가 성립하면 해당 후보는 어떤 이후 단계에서도 최적해에 기여하지 못합니다. 예를 들어 더 작고 더 왼쪽에 있는 후보는, 더 큰 값이 등장한 순간부터 다음 큰 수의 답 후보에서 탈락합니다.

단조 구조 패턴의 운영 영향

브루트포스로 매 위치마다 주변을 탐색하면 보통 O(N^2)가 됩니다.
단조 구조는 미래에 절대 답이 될 수 없는 원소를 즉시 삭제해 중복 탐색을 제거합니다.

이 패턴의 본질은 자료구조 이름보다 후보 집합 pruning에 있습니다. 지금 문제에서 앞으로 답이 될 수 없는 원소 조건을 문장으로 한 줄 적어 보세요.

단조 불변식 디버깅 시나리오

여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.

nums=[2, 1, 3]로 다음 큰 수를 직접 추적해 봅니다.

2를 스택에 넣습니다.
1은 top(2)보다 작으므로 그대로 push합니다.
3을 만나면 1, 2가 순서대로 pop되며 답이 3으로 확정됩니다.
각 인덱스가 최대 한 번 push/pop되므로 전체는 선형 시간입니다.

다음 큰 수(Next Greater Element)

문제 의도: 단조 스택으로 오른쪽에서 처음 더 큰 값을 선형 시간에 찾습니다.
입력 예시: nums=[2,1,2,4,3]
출력 예시: [4,2,4,-1,-1] push는 후보 인덱스를 쌓고, pop은 답이 확정된 인덱스를 제거합니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> nextGreater(const vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    vector<int> ans(n, -1);
    vector<int> st; // index stack

    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[st.back()] < nums[i]) {
            int idx = st.back();
            st.pop_back();
            ans[idx] = nums[i];
        }
        st.push_back(i);
    }
    return ans;
}

int main() {
    vector<int> ans = nextGreater({2, 1, 2, 4, 3});
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    static int[] nextGreater(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> st = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && nums[st.peek()] < nums[i]) {
                int idx = st.pop();
                ans[idx] = nums[i];
            }
            st.push(i);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreater(new int[]{2, 1, 2, 4, 3})));
    }
}

main.py

def next_greater(nums):
    n = len(nums)
    ans = [-1] * n
    st = []  # 인덱스 스택

    i = 0
    while i < n:
        x = nums[i]
        while st and nums[st[-1]] < x:
            idx = st.pop()
            ans[idx] = x
        st.append(i)
        i += 1

    return ans

print(next_greater([2, 1, 2, 4, 3]))  # [4, 2, 4, -1, -1]

main.rs

fn next_greater(nums: &[i32]) -> Vec<i32> {
    let n = nums.len();
    let mut ans = vec![-1; n];
    let mut st: Vec<usize> = Vec::new();

    for i in 0..n {
        while let Some(&top) = st.last() {
            if nums[top] < nums[i] {
                st.pop();
                ans[top] = nums[i];
            } else {
                break;
            }
        }
        st.push(i);
    }
    ans
}

fn main() {
    println!("{:?}", next_greater(&[2, 1, 2, 4, 3]));
}

단조 스택/큐 확인 불변식 초기 확인

스택에는 아직 다음 큰 수를 못 찾은 인덱스만 남깁니다.
새 값 x가 스택 top보다 크면, 그 top의 답이 x로 확정됩니다.
각 인덱스는 한 번 push, 한 번 pop만 되므로 전체 시간은 O(N)입니다.

평균 시간복잡도: O(N)
최악 시간복잡도: O(N)
공간복잡도: O(N)

슬라이딩 윈도우 최댓값

문제 의도: 단조 큐로 각 윈도우의 최댓값을 재계산 없이 유지합니다.
입력 예시: nums=[1,3,-1,-3,5,3,6,7], k=3
출력 예시: [3,3,5,5,6,7] pop_front는 범위를 벗어난 인덱스를 제거하고, pop_back은 더 작은 후보를 지웁니다.

main.cpp

#include <deque>
#include <iostream>
#include <vector>
using namespace std;

vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;

    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) result.push_back(nums[dq.front()]);
    }

    return result;
}

int main() {
    vector<int> ans = maxSlidingWindow({1, 3, -1, -3, 5, 3, 6, 7}, 3);
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static List<Integer> maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.removeFirst();
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.removeLast();
            dq.addLast(i);
            if (i >= k - 1) result.add(nums[dq.peekFirst()]);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3));
    }
}

main.py

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # 값이 큰 인덱스를 앞에 유지
    result = []

    i = 0
    while i < len(nums):
        x = nums[i]
        # 윈도우 밖 인덱스 제거
        while dq and dq[0] <= i - k:
            dq.popleft()

        # 현재 값보다 작은 후보 제거
        while dq and nums[dq[-1]] <= x:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])
        i += 1

    return result

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

main.rs

use std::collections::VecDeque;

fn max_sliding_window(nums: &[i32], k: usize) -> Vec<i32> {
    let mut dq: VecDeque<usize> = VecDeque::new();
    let mut result = Vec::new();

    for i in 0..nums.len() {
        while let Some(&front) = dq.front() {
            if front + k <= i {
                dq.pop_front();
            } else {
                break;
            }
        }
        while let Some(&back) = dq.back() {
            if nums[back] <= nums[i] {
                dq.pop_back();
            } else {
                break;
            }
        }
        dq.push_back(i);
        if i + 1 >= k {
            if let Some(front_idx) = dq.front() {
                result.push(nums[*front_idx]);
            }
        }
    }
    result
}

fn main() {
    println!("{:?}", max_sliding_window(&[1, 3, -1, -3, 5, 3, 6, 7], 3));
}

단조 스택/큐 확인 연산 순서 추적

큐 앞쪽은 항상 현재 윈도우의 최댓값 인덱스입니다.
뒤쪽에서는 현재 값보다 작은 후보를 제거해 앞으로 최댓값이 될 가능성이 없는 원소를 버립니다.
윈도우 경계를 벗어난 인덱스를 우선 제거하는 순서가 매우 중요합니다.

평균 시간복잡도: O(N)
최악 시간복잡도: O(N)
공간복잡도: O(K)

단조 스택 표현 판정 축

단조 패턴을 적용할 수 있는지 판단하는 신호입니다.

각 위치에서 가장 가까운 더 큰/작은 값을 구한다
고정 길이 구간의 최댓값/최솟값을 반복 계산한다
앞선 후보가 뒤 원소에 의해 완전히 지배될 수 있다

이 신호가 보이면 단조 스택/큐를 우선 검토합니다.

단조 유지 로직 구현 복잡도 상충

단조 구조는 빠르지만 구현 실수에 민감합니다.

장점: 선형 시간으로 큰 성능 개선
단점: 경계 인덱스 조건이 복잡해 디버깅 난이도 증가
장점: 후보 집합이 작아 메모리 효율적
단점: 문제 조건이 조금만 달라져도 코드 수정이 크게 필요

정확한 조건 정의 없이 복사 붙여넣기하면 오답 확률이 높습니다.

주식 가격 지속 기간(단조 스택 변형)

문제 의도: 값이 떨어질 때까지의 구간 길이를 단조 스택 변형으로 계산합니다.
입력 예시: prices=[1,2,3,2,3]
출력 예시: [4,3,1,1,0]

아래 문제는 현재 값보다 작은 값이 처음 나올 때까지의 길이를 계산하는 전형적인 변형입니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> priceDuration(const vector<int>& prices) {
    int n = static_cast<int>(prices.size());
    vector<int> ans(n, 0);
    vector<int> st;

    for (int i = 0; i < n; ++i) {
        while (!st.empty() && prices[st.back()] > prices[i]) {
            int j = st.back();
            st.pop_back();
            ans[j] = i - j;
        }
        st.push_back(i);
    }
    while (!st.empty()) {
        int j = st.back();
        st.pop_back();
        ans[j] = n - 1 - j;
    }
    return ans;
}

int main() {
    vector<int> ans = priceDuration({1, 2, 3, 2, 3});
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    static int[] priceDuration(int[] prices) {
        int n = prices.length;
        int[] ans = new int[n];
        Deque<Integer> st = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && prices[st.peek()] > prices[i]) {
                int j = st.pop();
                ans[j] = i - j;
            }
            st.push(i);
        }
        while (!st.isEmpty()) {
            int j = st.pop();
            ans[j] = n - 1 - j;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(priceDuration(new int[]{1, 2, 3, 2, 3})));
    }
}

main.py

def price_duration(prices):
    n = len(prices)
    ans = [0] * n
    st = []  # 인덱스

    i = 0
    while i < n:
        p = prices[i]
        while st and prices[st[-1]] > p:
            j = st.pop()
            ans[j] = i - j
        st.append(i)
        i += 1

    while st:
        j = st.pop()
        ans[j] = n - 1 - j

    return ans

print(price_duration([1, 2, 3, 2, 3]))  # [4, 3, 1, 1, 0]

main.rs

fn price_duration(prices: &[i32]) -> Vec<i32> {
    let n = prices.len();
    let mut ans = vec![0i32; n];
    let mut st: Vec<usize> = Vec::new();

    for i in 0..n {
        while let Some(&top) = st.last() {
            if prices[top] > prices[i] {
                st.pop();
                ans[top] = (i - top) as i32;
            } else {
                break;
            }
        }
        st.push(i);
    }
    while let Some(j) = st.pop() {
        ans[j] = (n - 1 - j) as i32;
    }
    ans
}

fn main() {
    println!("{:?}", price_duration(&[1, 2, 3, 2, 3]));
}

단조 스택/큐 확인 실패사례 재실행 확인

값이 떨어지는 순간에만 이전 인덱스의 답을 확정합니다.
마지막까지 떨어지지 않은 인덱스는 후처리에서 배열 끝 기준으로 계산합니다.
단조 스택 패턴은 유지하되, 답 확정 시점이 문제별로 달라진다는 점이 중요합니다.

평균 시간복잡도: O(N)
최악 시간복잡도: O(N)
공간복잡도: O(N)

패턴 식별 체크

다음 질문에 예가 많으면 단조 구조 가능성이 높습니다.

이전/다음 더 큰(작은) 원소를 빠르게 찾는가?
한 번 버린 후보가 다시 필요하지 않은가?
창(window) 이동 시 오래된 후보를 제거할 수 있는가?
답이 인덱스 기반 거리로 표현되는가?

이 체크를 우선 하면 불필요한 O(N^2) 시도를 줄일 수 있습니다. 또한 동점 처리 규칙을 우선 정해두면 </<= 혼동을 줄일 수 있습니다. 문제에서 요구하는 엄격 비교인지 비엄격 비교인지를 명시적으로 고정하는 습관이 중요합니다. 이 한 줄 정책 메모가 디버깅 시간을 크게 줄입니다.