백준 2493번 탑 JAVA

링크텍스트

설명

처음에는 Stack을 사용하지않고 풀어 시간초과가 났다. Stack을 사용하면 stack.peek()[0] → 탑의 높이, stack.peek()[1] → 탑의 인덱스(탑 번호)를 저장할 수 있어 시간초과 나지않게 문제를 풀 수 있다.
시간복잡도: O(N), 공간복잡도: O(N)

코드

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

class Main {
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringBuilder sb = new StringBuilder();
	    
	    int n = Integer.parseInt(br.readLine());
	    int [] arr = new int[n];
	    
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    for(int i=0;i<n;i++){
	        arr[i] = Integer.parseInt(st.nextToken());
	    }

		Stack<int []> stack = new Stack<>();

		for(int i=0;i<n;i++){
			while(!stack.isEmpty() && stack.peek()[0] <arr[i]){
				stack.pop();
			}

			if(stack.isEmpty()){
				sb.append(0).append(" ");
			}else{
				sb.append(stack.peek()[1]).append(" ");
			}

			stack.push(new int[]{arr[i],i+1});
		}
	    
	   System.out.print(sb);
	}
}