[알고리즘] 백준 - 탑

백준 - 탑

내 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;


public class baekjoon_2493 {

    static int N;
    static int[] arr;
    static int[] ansArr;
    static Stack<Integer> stack = new Stack<>();

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

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        ansArr = new int[N];

        String[] inputs = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(inputs[i]);
        }

        for (int i = N - 1; i >= 0; i--) {

            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                ansArr[stack.pop()] = i+1;
            }
            stack.add(i);
        }
        for (int num : ansArr) {
            bw.write(num + " ");
        }
        bw.flush();
        bw.close();
    }
}

문제대로 제일 오른쪽에서부터 시작한다. 스택에는 높이가 아닌 인덱스를 저장한다 (인덱스만 있으면 높이는 언제든지 조회 가능하다). 만약 스택의 제일 위에 있는 인덱스의 높이보다 현재 인덱스가 높다면 현재 타워에 레이저가 도달하는 것이다. 그래서 그 조건이 만족하는 동안 스택에서 팝하며 팝된 인덱스에 현재 인덱스를 넣는다. 스택에는 항상 밑의 인덱스 높이보다 작은 타워의 인덱스들만 쌓일 것이다.