[백준 - JAVA] 2493번 : 탑

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

2493번: 탑

처음에는 단순히 값 비교를 하나하나 하는 방식을 생각했는데 최악의 경우 500000^2 회 비교를 해야하기 때문에 시간초과가 날 것 같았다.

매번 전부를 계산하는 것은 안되고 진행 과정 중간에 쳐낼 수 있는 것은 쳐내야 했는데 스택에 쌓으면서 전에 있던 숫자보다 크다면 더 이상 스택에 쌓아놓을 필요가 없다는 것을 알았다.

새로운 숫자가 들어올 때 본인보다 작으면 버리고 본인보다 크면 위에 쌓는 식으로 진행했다.

결과 값은 탑의 번호로 출력하게 되는데 그렇다면 탑의 높이, 탑의 순서 두 가지 (int 2개)를 들고 다녀야 한다.

배열도 사용할 수 있겠지만 의미상으로 보기 쉬운 class를 이용했다.

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

class Node {
    int order;
    int num;

    Node(int order, int num) {
        this.order = order;
        this.num = num;
    }
}

public class Q_2493 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static Stack<Node> stack = new Stack<>();

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

        for(int i = 1; i <= N; i++) {
            int next = Integer.parseInt(st.nextToken());
            check(new Node(i, next));
        }

        bw.close();
    }

    private static void check(Node next) throws IOException {
        //본인보다 큰 것이 나올 때 까지 꺼내고 큰게 나오면 그 위에 들어가
        while(!stack.isEmpty()) {
            Node top = stack.peek();

            if(top.num > next.num) {
                bw.write(top.order + " ");
                stack.push(next);
                return;
            }

            stack.pop();
        }

        //끝까지 안나올 때
        bw.write(0 + " ");
        stack.push(next);
    }
}