백준 2493 탑

처음 투포인터로 배열을 접근하는 방식으로 했다가 시간초과가 났다. 

고민하다가 스택으로 풀었다. 왼쪽에서 오른쪽으로 가면서 스택에는 인덱스를 저장하는데 현재 값보다 작은 값이 저장될 필요가 없기에 빼주며 항상 값은 삽입한다. (스택의 제일 위보다 현재 값이 낮더라도 다음 값보다는 클 수 있기 떄문)

다르게는 인덱스와 탑 높이를 저장하는 클래스를 생성하여 이용할 수도 있겠다. 

package day0804;

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

public class Top {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bf.readLine());

		String s = bf.readLine();
		StringTokenizer st = new StringTokenizer(s);
		int[] ans = new int[n]; //정답 배열
		int[] arr = new int[n]; // 탑 높이가 저장된 배열
		Stack<Integer> index = new Stack<>(); // 탑의 인덱스가 저장된 스택

		for (int i = 0; i < n; i++) {
			int cur = Integer.parseInt(st.nextToken()); //현재 탑의 높이
			arr[i] = cur;
			if (index.empty()) {//스택이 비어있으면
				index.push(i); //현재값을 넣고
				ans[i] = 0; //신호를 받을 탑이 없으므로 0 삽입
			} else {

				while (!index.empty()) { //스택에 값이 있으면
					int firstIndex = index.peek(); // 가장 근접한 탑과 비교
					if (arr[firstIndex] < cur) { //현재 탑보다 낮으면
						index.pop(); //뺴준다
					} else {//높은 탑이 있으면
						ans[i] = firstIndex + 1; //값을 넣어준다

						break;
					}
				}
				index.push(i);  // 스택에 현재 값 삽입

			}

		}

		ans[0] = 0;
		for (int i = 0; i < n; i++) {
			System.out.print(ans[i] + " ");
		}
	}

}