[백준] 2493 탑 java

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


class Top {
    int loc;
    int len;
    Top(int loc, int len) {
        this.loc = loc;
        this.len = len;
    }
}

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int n;
    static int[] tops;
    static Stack<Top> s = new Stack<>();
    static StringBuilder ans = new StringBuilder();

    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.println(ans.toString());
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        tops = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            tops[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void solve() {
        ans.append("0 ");
        s.push(new Top(1, tops[0]));
        for(int i = 1; i < n; i++) {
            while(true) {
                if(s.isEmpty()) {
                    ans.append("0 ");
                    s.push(new Top(i+1, tops[i]));
                    break;
                }
                if(tops[i] < s.peek().len) {
                    ans.append(s.peek().loc + " ");
                    s.push(new Top(i+1, tops[i]));
                    break;
                }
                else {
                    s.pop();
                }
            }
        }
    }
}

스택을 이용한 문제였다.

 

스택이 비어있다면 현재 위치의 탑보다 큰 탑이 없으므로 0을 출력한다.

 

그 외의 2가지 케이스로는 현재 위치의 탑이 peek한 탑의 높이보다 높거나 같은 경우 스택에서 pop한다.

반대로 현재 위치의 탑이 peek한 탑의 높이보다 작을 경우 peek한 탑의 위치를 출력하고 현재 위치의 탑을 push한다.