백준 탑(2493번)

알고리즘

높이를 입력받으면서 현재 스택의 맨위 높이가 입력받은 높이보다 높은지 확인

높다면 신호를 받을수 없기 때문에 pop을 시키고 계속해서 확인한다.

스택의 맨 위에있는 높이보다 입력받은 높이가 낮다면 신호를 받을 수 있기 때문에 

스택의 맨위에 있는 건물의 번호를 출력시킨다.

(스택이 비어있을 때 같은 예외 처리도 포함)

 

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());	
		StringTokenizer st = new StringTokenizer(br.readLine());
		Stack<int[]> s = new Stack<int[]>();
		
		for (int i =1; i<= num; i++) {	//1부터 건물의 개수만큼 반복
			int height = Integer.parseInt(st.nextToken());	// 건물의 높이 입력 받기
			while(!s.empty()) {	// 스택이 비어있지 않다면 반복
				if(s.peek()[0]<height) {	// 현재 건물 전의 높이가 더 낮다면 실행
					s.pop();	// 신호를 받을 수 없는 건물이므로 제거
				}else {	// 현재 건물 전의 높이가 더 높다면 실행
					System.out.print(s.peek()[1]+" ");	//해당 건물의 번호 출력 
					break;	//신호를 주었다면 더이상 반복할 필요가 없음
				}
			}
			if(s.empty()) {	//스택이 비어있다면
				System.out.print("0 ");	// 신호를 줄수 있는 건물이 없음
			}
			s.push(new int[] {height, i});	// 스택에 현재 건물의 높이와 건물의 번호를 넣는다.
		}
	}
}