백준 17298번 오큰수

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

public class NGE {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            while(!stack.isEmpty()){
                if(arr[stack.peek()]<arr[i]){
                    arr[stack.pop()] = arr[i];
                }
                else break;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()){
            arr[stack.pop()] = -1;
        }
        for (int i = 0; i < N; i++) {
            sb.append(arr[i]).append(' ');
        }
        System.out.println(sb);
    }
}

풀이방법

1. 스택에 현재 인덱스를 담으며 진행하고,
   while문으로 스택을 탐색하며, 스택에 담긴 인덱스에 해당하는 arr값이 현재 arr값보다 작으면 그곳에 현재 arr값을 대입하며 진행한다.
   현재 arr값보다 크다면, while문을 탈출한다.
2. 처리되지 못하고 stack에 남아있는 인덱스는 오큰수가 없다는 뜻이므로, -1 처리해준다

후기

사실 그냥 이중포문 구현하면 쉽지만, 시간초과때문에 해당 원리로 풀어야 하는 문제이다.
스택에 인덱스를 넣고, arr값을 바꾸면서 진행하는 원리를 깨닫는것이 어려운 문제다.
이런 풀이가 정해진 문제를 좋아하진 않지만, stack의 활용법을 배울 수 있었다.