"이 배열에서 각 원소의 오른쪽에 있는 첫 번째 더 큰 수를 구하라." 이 문제를 처음 보면 대부분 이중 for문을 떠올린다. 돌아간다. 맞다. 근데 N이 100만이면? O(n²)은 TLE 직행이다. 여기서 모노토닉 스택이 등장한다.

모노토닉 스택이 뭔데

스택인데, 원소를 넣을 때 특정 순서(오름차순 또는 내림차순)를 유지하는 스택이다. 새 원소가 들어올 때 순서를 깨는 기존 원소를 전부 pop한다. 그게 전부다.

핵심 아이디어를 한 문장으로: "나보다 작은(또는 큰) 놈이 나타나는 순간을 포착하는 도구."

이걸로 할 수 있는 일들:

  • Next Greater Element (오른쪽에서 나보다 큰 첫 번째 원소)

  • Next Smaller Element

  • 히스토그램에서 가장 큰 직사각형

  • 주식 가격 스팬

  • 일일 온도 문제 (LeetCode 739)

겉모습은 전부 다르다. 근데 뜯어보면 "각 원소에 대해 특정 조건을 만족하는 가장 가까운 원소를 찾아라"는 같은 패턴이다. 이 패턴을 한번 체득하면 변형 문제가 나와도 30초 안에 접근법이 떠오른다.

Next Greater Element부터 해보자

가장 기본적인 유형이다. 배열 [2, 1, 2, 4, 3]이 주어졌을 때, 각 원소의 오른쪽에 있는 첫 번째 더 큰 수를 구한다. 없으면 -1.

def next_greater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # 인덱스를 저장

    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

# [2, 1, 2, 4, 3] → [4, 2, 4, -1, -1]

배열을 왼쪽에서 오른쪽으로 훑는다. 스택에는 "아직 자기보다 큰 수를 못 찾은 원소들의 인덱스"가 쌓여 있다. 새 원소가 스택 top보다 크면? 드디어 답을 찾은 거다. pop하면서 답을 기록한다.

각 원소가 스택에 최대 한 번 push, 한 번 pop. 전체 시간복잡도 O(n). 이중 for문 O(n²)에서 극적으로 줄어든다.

한 가지 짚고 넘어갈 점 — 이 코드를 처음 보면 while문 안에서 pop이 여러 번 일어나니까 "이거 O(n) 맞아?"라는 의문이 든다. 맞다. 전체 순회에서 모든 원소가 push 한 번, pop 한 번이니까 총 연산 횟수가 2n을 넘지 않는다. 이른바 상각 분석(amortized analysis)이다.

실전 — 히스토그램에서 가장 큰 직사각형

백준 6549, LeetCode 84. 코테 단골 중의 단골이다. 높이 배열 [2, 1, 5, 6, 2, 3]에서 막대들로 만들 수 있는 가장 큰 직사각형의 넓이를 구한다.

브루트포스로는 모든 쌍을 비교하면서 O(n²). 모노토닉 스택을 쓰면 O(n)에 끝난다.

def largest_rectangle(heights):
    stack = []
    max_area = 0
    heights.append(0)  # 센티널: 마지막에 스택 비우기용

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    heights.pop()  # 센티널 제거
    return max_area

스택은 오름차순을 유지한다(높이 기준). 현재 높이가 스택 top보다 낮으면, 그 top 높이로 만들 수 있는 직사각형의 최대 너비를 계산하고 pop한다.

heights.append(0)이 핵심 트릭이다. 높이 0짜리 가상의 막대를 끝에 붙이면, 순회가 끝날 때 스택에 남아있는 모든 원소가 자동으로 처리된다. 이 센티널 패턴은 모노토닉 스택 문제에서 반복적으로 등장하니까 익숙해지면 좋다.

이 문제가 모노토닉 스택의 본질을 가장 잘 보여준다. "지금까지 쌓아온 것 중에서, 현재 상황에서 더 이상 확장할 수 없는 것을 처리한다." 이 사고방식이 체화되면 변형 문제도 뚫린다.

언제 모노토닉 스택을 의심할까

문제를 읽었을 때 아래 신호가 보이면 모노토닉 스택을 먼저 떠올리자:

  • "각 원소에 대해" + "가장 가까운" + "더 크거나 작은"

  • 배열 한쪽 방향으로 특정 조건의 첫 원소 찾기

  • 히스토그램, 건물, 탑처럼 높이가 핵심인 문제

  • N ≥ 10⁵인데 O(n) 또는 O(n log n)을 요구하는 느낌

반대로 이건 모노토닉 스택이 아니다: "k번째로 큰 수"는 힙이나 정렬 영역이고, 구간 최솟값/최댓값 쿼리가 반복되면 세그먼트 트리 쪽이다. 모노토닉 스택은 한 번 순회하면서 각 원소의 답을 확정할 수 있을 때 쓴다. 답이 순회 중에 바뀌거나 여러 쿼리에 대응해야 하면 다른 자료구조를 봐야 한다.

자주 실수하는 두 가지

값 vs 인덱스. 스택에 값을 넣을지 인덱스를 넣을지 고민되면, 인덱스를 넣어라. 값만 넣으면 나중에 위치 정보가 필요할 때 난감해진다. 히스토그램 문제에서 너비 계산이 불가능해지는 게 대표적 사례다. 인덱스를 넣으면 nums[stack[-1]]로 값도 바로 꺼낼 수 있으니까 손해 볼 게 없다.

오름차순 vs 내림차순 혼동. 더 큰 수를 찾는 문제면 오름차순 스택(작은 수가 바닥), 더 작은 수를 찾는 문제면 내림차순 스택. 새로 들어오는 원소가 조건을 만족시키는 순간 pop이 터져야 하니까 이 방향이 맞다. 헷갈리면 3개짜리 배열로 직접 손시뮬 돌려보는 게 가장 빠르다.

4월 코테 시즌이다. 삼성 SW 역량테스트도 이달 중 예정이고, 각종 공채 코테가 줄줄이 잡혀 있다. 모노토닉 스택은 한번 잡아두면 의외로 자주 꺼내 쓰게 되는 무기다. 오늘 Next Greater Element 하나, 히스토그램 하나만 직접 짜보자.