[백준 - JAVA] 17298번 : 오큰수

 

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

17298번: 오큰수

사실 얼마 전에 풀었던 탑 문제와 개념적으로 아예 같은 문제라 금방 풀었다.

100만개를 전부 비교하면 시간복잡도 N^2 이라 시간이 부족할 것이고 스택을 사용해 비교할 필요가 없는 부분들은 제거하면서 확인했다.

 

https://godhkekf24.tistory.com/93

[백준 - JAVA] 2493번 : 탑

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

public class Q_17298 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static Stack<Integer> stack = new Stack<>();
    static int[] arr, result;

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

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

        for(int i = arr.length - 1; i >= 0; i--) {
            result[i] = check(arr[i]);
        }

        for(int i = 0; i < result.length; i++) {
            bw.write(result[i] + " ");
        }
        bw.close();

    }

    private static int check(int num) {
        //본인보다 큰 것이 나올 때까지 꺼내서 확인
        while(!stack.isEmpty()) {
            int next = stack.peek();
            if(next <= num) {
                stack.pop();
                continue;
            }

            //큰 것이 나왔을 때
            stack.push(num);
            return next;
        }

        // 전부 비었을 때
        stack.push(num);
        return -1;
    }
}