kingsubin

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class boj_17298 {
    static Stack<Integer> s = new Stack<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] nge = new int[n];

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

        for (int i = 0; i < arr.length; i++) {
            if (s.isEmpty()) {
                s.push(i);
            }

            // 현재의 값이 스택의 top보다 크다면 현재값이 오큰수
            while (!s.isEmpty() && arr[i] > arr[s.peek()]) {
                nge[s.pop()] = arr[i];
            }
            s.push(i); // 현재 값도 오큰수를 구해야하니 스택에 Push
        }

        // 위에 과정을 거쳤는데도 스택에 쌓여있다는것은 오큰수가 없다는 뜻
        while (!s.isEmpty()) {
            nge[s.pop()] = -1;
        }

        // 출력
        for (int value : nge) {
            sb.append(value).append(" ");
        }
        System.out.println(sb.toString());
    }
}

- 어렵다,,,,

 

- 스택 생각

- 오큰수라는 것은 인덱스와 값이 크면서 인덱스가 제일 작은 값

- 그러니까 나 다음 첫번째에 등장하는 큰 수라고 생각