BOJ_G5_2493

📁 [G5_2493] 탑

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

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		Stack<Integer> rootStack = new Stack<>();
		Stack<Integer> indexStack = new Stack<>();
		
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int first = Integer.parseInt(st.nextToken());
		rootStack.push(first);
		indexStack.push(1);
		sb.append("0 ");
		
		for(int i=2; i<=N; i++) {
			int value = Integer.parseInt(st.nextToken());
			
			while(!rootStack.isEmpty()) {
				// stack에 있는 값이 새로 push 되려는 값보다 클 경우
				if(value < rootStack.peek()) {
					sb.append(indexStack.peek() + " ");
					break;
				}
				// stack에 있는 값이 새로 push 되려는 값보다 작을 경우
				rootStack.pop();
				indexStack.pop();
			}
			
			// stack이 비어있을 경우
			if(rootStack.isEmpty()) {
				sb.append("0 ");
			}
			rootStack.push(value);
			indexStack.push(i);
		}
		System.out.println(sb.toString());
	}	
}

🤔 나의 생각

처음에 2중 for문으로 풀었는데 역시 N이 큰 탓인지 시간, 메모리 오류가 떴다.
그래서 방법을 고민하다가 도저히 생각이 안나서 구글링을 통해 STACK을 통해 푸는 방법을 알게 되었다..
두 개의 STACK을 이용해 index와 탑의 높이를 push하려는 값이 더 큰경우, 작은경우, STACK이 빈 경우를 나눠서 풀어주었다.