java - 백준 알고리즘 - 2493 탑

이 문제는 자료구조 Stack을 이용하는 문제이다.

왼쪽부터 차례대로 Stack에 하나씩 넣으면서 스텍의 Top 값과 비교해주면 된다.

인덱스를 출력하기 위해서 높이와 인덱스 2개의 stack을 사용하였다.

스텍에 넣을 값 = now, 스텍의 top 값 = top

 

1. top > now 일때

Top의 index를 버퍼에 담고 now를 hight, index 스텍에 push 해준다.

2. now <= top 일때

hight, index 스텍에서 top을 제거해준다. (pop)

 

이 과정을 반복 한 후 stack이 비었을때는 0을 출력해주면 된다.

 

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

public class Main {

	static int N;
	static int[] arr;
	static Stack hight = new Stack();
	static Stack index = new Stack();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		arr = new int[N + 1];
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str, " ");

		for (int i = 1; N >= i; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		hight.push(arr[1]);
		index.push(1);
		bw.write(""+0);

		for (int i = 2; N >= i; ++i) {
			while (true) {
				if (!hight.isEmpty()) {
					int top = hight.peek();
					if (top > arr[i]) {
						bw.write(" " + index.peek());
						hight.push(arr[i]);
						index.push(i);
						break;
					} else {
						hight.pop();
						index.pop();
					}
				} else {
					bw.write(" " + 0);
					hight.push(arr[i]);
					index.push(i);
					break;
				}
			}
		}
		bw.flush();
	}
}