[백준] 17298: 오큰수 (Java)

문제

https://www.acmicpc.net/problem/17298

접근 방법

1. 입력받은 수의 값을 저장할 스택과, 인덱스를 저장할 스택 2개를 만들었다.
2. 값에 마지막에 저장된 수보다 지금 입력이 더 크다면 출력 배열에 pop된 인덱스에 지금 입력을 저장.
3. 모든 입력이 끝나고 스택에 남아있는 값들은 -1로 저장.

풀이 코드

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

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));
        BufferedWriter bw2 = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<Integer> stk = new Stack<>();
        Stack<Integer> stk_idx = new Stack<>();

        int[] arr = new int[1000000];
        int num;
        for (int i = 0; i < N; i++){
            num = Integer.parseInt(st.nextToken());
            while (!stk.empty() && stk.peek() < num){
                stk.pop();
                arr[stk_idx.pop()] = num;
            }
            stk.push(num);
            stk_idx.push(i);
        }
        while(!stk.empty()){
            stk.pop();
            arr[stk_idx.pop()] = -1;
        }
        for (int i = 0; i < N; i++) {
            bw.write(arr[i] + " ");
        }

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