bj17298(오큰수)-스택

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

 

이 문제는 아주 쉬운 문제였다.

stack의 특성 상

아직 처리가 안된 것들을 스택이라는 버퍼에 담고(아직 큰 것들이 안나온것)

큰 것이 나오면 처리해준다.

스택을 선택해준 이유는

처리가 안될 수록 큰 수이기 때문에, 우선순위가 뒤로 밀려야 했다.

PQ로 해주었어도 됐겠지만, 시간 복잡도로 인해

스택을 써주었다.

** System.out.println()을 써주면 시간 초과가 나니, BufferedWriter를 쓰자.**

 

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

public class Main {
    static int N;
    static Stack<int[]> nums = new Stack<>();
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        initialize();
        int[] answers = solve();
        print(answers);
        bufferedReader.close();
        bufferedWriter.close();
    }

    private static void print(int[] answers) throws IOException {
        for(int i = 0; i < N; i++){
            bufferedWriter.write(String.valueOf(answers[i]+ " "));
        }
        bufferedWriter.flush();
    }

    private static int[] solve() throws IOException {
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int[] answers = new int[N];
        for(int i = 0; i < N; i++){
            int temp = Integer.parseInt(stringTokenizer.nextToken());
            while(!nums.isEmpty() && nums.peek()[1] < temp){
                int[] curr = nums.pop();
                answers[ curr[0] ] = temp;
            }
            nums.add(new int[]{i, temp});
        }
        disposeRemain(answers);
        return answers;
    }

    private static void disposeRemain(int[] answers) {
        while(!nums.isEmpty()){
            int[] temp = nums.pop();
            answers[temp[0]] = -1;
        }
    }

    private static void initialize() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
    }
}