[BOJ 2493] 탑 (Java)

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

2493번: 탑

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static Stack<Node> stack=new Stack<>();
	static int[] arr;
	static int[] ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr=new int[N+1];
		ans=new int[N+1];
		for (int i=1; i<=N; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		stack.push(new Node(1,arr[1]));
		for (int i=2; i<=N; i++) {
			while (!stack.isEmpty()) {
				if (stack.peek().val>=arr[i]) {
					ans[i]=stack.peek().num;
					break;
				}
				else {
					stack.pop();
				}
			}
			stack.push(new Node(i,arr[i]));
			
		}
		for (int i=1; i<=N; i++) {
			System.out.print(ans[i]+" ");
		}
		
	}
	static class Node{
		int num;
		int val;
		private Node(int num, int val) {
			this.num = num;
			this.val = val;
		}
		
	}

}

아이디어를 떠올리기가 쉽지 않아 힌트를 참고했다.

1번째 수를 먼저 스택에 넣어 준다. 

2번째부터 N번째 수까지, 다음과 같은 과정을 반복한다.

1. 자기보다 크거나 같은 값이 있으면 멈추고 값을 저장한다.

2. 자기보다 작은 값이 있으면 스택에서 pop 시킨다.

멈추거나 스택이 비게 되면, 자기 값을 스택에 넣는다.