백준 17298번 오큰수 [ Java ]

17298번: 오큰수

 

오른쪽에 있는 큰 수 중 가장 왼쪽에 수를 찾는건데 가장 먼저 떠오르는 방법은 현재 인덱스부터 오른쪽을 전부 검사하는 것이다.

하지만 이렇게 하면 O(n^2)의 시간복잡도가 나와서 시간초과가 나오게 된다.

스택을 이용하면 O(n)으로 풀 수 있다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int res[] = new int[N];
        int num[] = Arrays.stream(br.readLine().split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray();

        for (int i = 0; i < N; i++) {
            if (stack.isEmpty())
                stack.push(i);
            while (!stack.isEmpty() && num[stack.peek()] < num[i])
                res[stack.pop()] = num[i];
            stack.push(i);
        }
        while (!stack.isEmpty())
            res[stack.pop()] = -1;
        for (int i : res)
            sb.append(i + " ");
        System.out.print(sb);
    }
}