[백준 17298] 오큰수 (Java) - 모노톤 스택(Monotonic Stack) 활용하기

🚀 문제 핵심 파악

각 원소 $A_i$에 대해, 오른쪽에 있으면서 $A_i$보다 큰 수 중 가장 왼쪽에 있는 수(오큰수)를 찾아야 합니다.

• 데이터 규모: $N \le 1,000,000$ (100만)
• 시간 복잡도 제약: 단순 중첩 반복문($O(N^2)$)은 불가능하며, 반드시 $O(N)$ 내에 해결해야 합니다.

---

💡 해결 전략: 모노톤 스택 (Monotonic Stack)

스택 내부를 특정 순서(이 문제에서는 내림차순)로 유지하며, 조건이 맞을 때 '한꺼번에' 처리하는 모노톤 스택 기법을 사용합니다.

1. 인덱스 스택(Index Stack): 스택에 값 자체가 아닌 인덱스를 쌓습니다. 그래야 나중에 오큰수를 찾았을 때 NGE[index] 위치에 정확히 값을 기록할 수 있습니다.
2. 모노톤 유지 (While): 현재 숫자($A[i]$)가 스택의 top에 있는 인덱스의 값보다 크다면?

• 스택에 대기 중이던 녀석들이 드디어 자신보다 큰 녀석($A[i]$)을 만난 상황입니다.
• pop을 수행하며 해당 인덱스의 오큰수를 $A[i]$로 확정 짓습니다.

3. 결과 보장: 모든 순회가 끝났는데도 스택에 남아있는 인덱스들은 오른쪽에 큰 수가 없다는 뜻입니다. (미리 -1로 초기화하여 효율적으로 처리합니다.)

---

💻 구현 코드 (Java)

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

public class Main {
    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            
            int N = Integer.parseInt(br.readLine());
            int[] A = new int[N];
            int[] NGE = new int[N];
            
            // 아직 오큰수를 찾지 못한 경우를 위해 -1로 초기화
            Arrays.fill(NGE, -1);

            StringTokenizer st = new StringTokenizer(br.readLine());
            // [Key] 인덱스를 담을 모노톤 스택 (ArrayDeque 권장)
            Deque<Integer> stack = new ArrayDeque<>();

            for (int i = 0; i < N; i++) {
                A[i] = Integer.parseInt(st.nextToken());

                // 스택이 비어있지 않고, 현재 값이 스택 top이 가리키는 값보다 크다면
                // 현재 값은 '오큰수'가 됨
                while (!stack.isEmpty() && A[stack.peek()] < A[i]) {
                    NGE[stack.pop()] = A[i];
                }

                // 현재 인덱스를 스택에 추가
                stack.push(i);
            }

            // 출력 최적화: StringBuilder 사용
            StringBuilder sb = new StringBuilder();
            for (int val : NGE) {
                sb.append(val).append(" ");
            }
            bw.write(sb.toString());
            bw.flush();
        }
    }
}

---

🧐 기술적 통찰 (Self-Note)

• 왜 모노톤 스택인가?: 스택 내부가 값 기준으로 보면 '내림차순'을 유지하게 됩니다($A[stack.peek()] \ge A[i]$ 일 때만 push하니까요). 그러다 더 큰 값이 나타나는 순간(A[i]가 더 클 때) 모노톤이 깨지면서 그동안 쌓여있던 작은 값들의 오큰수가 결정되는 원리입니다.
• 효율성: 모든 원소는 스택에 딱 한 번 들어갔다 나옵니다. 연산 횟수는 정확히 $2N$번에 수렴하므로 $O(N)$의 성능을 보장합니다.
• 출력 팁: $N$이 100만일 때는 System.out.print를 쓰면 안 됩니다. 반드시 StringBuilder나 BufferedWriter를 사용해야 시간 초과를 피할 수 있습니다.

---

🎯 마무리

11003번에서 다뤘던 모노톤 덱과 이번 모노톤 스택은 '불필요한 비교를 줄이고 유의미한 데이터만 자료구조에 유지한다'는 핵심 아이디어를 공유합니다. 선형 자료구조를 활용한 시간 복잡도 최적화의 정수를 맛볼 수 있는 좋은 문제였습니다.