[BOJ] 2493. 탑

문제 원본 : https://www.acmicpc.net/problem/2493

2493번: 탑

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] ans = new int[n];
        int[] top = new int[n];
        int[] topIdx = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; ++i) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int idx = -1;
        for (int i = 0; i < n; ++i) {
            while (idx > -1 && top[idx] < arr[i]) {
                --idx;
            }

            if (idx == -1) {
                ans[i] = 0;
            } else {
                ans[i] = topIdx[idx];
            }

            top[++idx] = arr[i];
            topIdx[idx] = i + 1;
        }

        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            builder.append(ans[i]).append(" ");
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }
}

• 스택을 활용한 문제
• 오큰수 문제랑 똑같은데 방향만 바뀌고 탑의 높이가 아니라 번호를 출력해야 한다.
• Stack 클래스보다 배열을 활용하는 게 더 빠른 것 같다.