[백준/Java] 17298 오큰수

문제

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

풀이방법

i = 0 (탑 높이 6) 스택: 비어있음 → answer[0] = 0 0번 인덱스 push (스택: [0])

i = 1 (탑 높이 9) 스택 top(0번, 6) < 9 → pop (스택: []) 스택 비어있음 → answer[1] = 0 1번 인덱스 push (스택: [1])

i = 2 (탑 높이 5) 스택 top(1번, 9) > 5 → answer[2] = 2 (1번 인덱스 + 1) 2번 인덱스 push (스택: [1, 2])

i = 3 (탑 높이 7) 스택 top(2번, 5) < 7 → pop (스택: [1]) 스택 top(1번, 9) > 7 → answer[3] = 2 (1번 인덱스 + 1) 3번 인덱스 push (스택: [1, 3])

i = 4 (탑 높이 4)

스택 top(3번, 7) > 4 → answer[4] = 4 (3번 인덱스 + 1) 4번 인덱스 push (스택: [1, 3, 4])

풀이

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));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] tower = new int[N];
        for (int i = 0; i<N; i++) {
            tower[i] = Integer.parseInt(st.nextToken());
        }
        int[] answer = new int[N];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && tower[stack.peek()] <= tower[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                answer[i] = 0;
            } else {
                answer[i] = stack.peek() + 1;
            }
            stack.push(i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(answer[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}