[백준]17289. 오큰수 - Java

📄 링크

boj 17298. 오큰수

---

💡 문제 분석

N * N으로 모든 경우를 비교하면 시간 초과가 납니다

O(N) 방법
순서대로 스택에 숫자를 넣을 때, 스택에 숫자가 들어있다면 현재 넣을 숫자와 비교해 봅니다
만약 현재 넣을 숫자가 더 크다면, 스택에 있는 숫자들의 오큰수는 현재 넣을 숫자가 됩니다
마지막 숫자까지 스택에 넣었다면 모든 오큰수를 구한 것이 됩니다.

---

⌨️ 코드

public class _17298_오큰수 {
    static class Pair {
        int idx, n;
        Pair(int idx, int n) {
            this.idx = idx;
            this.n = n;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        Pair[] arr = new Pair[N];
        int[] ret = new int[N];
        Arrays.fill(ret, -1);
        StringTokenizer st =  new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++)
            arr[i] = new Pair(i + 1, Integer.parseInt(st.nextToken()));
        ArrayDeque<Pair> stk = new ArrayDeque<>();
        for(Pair p : arr) {
            while (!stk.isEmpty() && stk.peekLast().n < p.n)
                ret[stk.pollLast().idx - 1] = p.n;
            stk.addLast(p);
        }
        for(int n : ret)
            sb.append(n).append(" ");
        System.out.println(sb);
    }
}

---

📋 결과