[BOJ] 17298. 오큰수

문제 원본 : https://www.acmicpc.net/problem/17298

17298번: 오큰수

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] nge = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; ++i) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> stack = new Stack<>();
        for (int i = n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && stack.peek() <= arr[i]) {
                stack.pop();
            }

            if (stack.isEmpty()) {
                nge[i] = -1;
            } else {
                nge[i] = stack.peek();
            }

            stack.push(arr[i]);
        }

        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            builder.append(nge[i]).append(" ");
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }
}

• 스택을 활용한 문제
• 스택에는 오름차순으로 숫자가 쌓이게 된다.
• 자신보다 큰 수가 나올 때까지 계속 pop을 하고,
• 스택이 비었으면 자신이 가장 크다는 말이므로 -1
• 마지막에는 자신을 스택에 push