[Java/백준/스택(Stack)] 2493번: 탑

문제

www.acmicpc.net/problem/2493

2493번: 탑

 

문제 이해에만 엄청 오래 걸렸다..

힌트를 봐도 당최 어떻게 푸는질 알아야지ㅠ

 

코드 자체는 단순하다.

 

탑이 나열되어 있을 때 가장 오른쪽에서 바라보면, 높은 건물들만 보인다.

 

탑 높이를 입력 받는다. → tall

(1-1) stack 확인, 비어있지 않다면 stack의 top의 높이를 확인한다. → tall보다 높다면 높은 탑의 위치를 출력하고 반복문을 빠져나온다.

(1-2) stack 확인, 비어있지 않다면 stack의 top의 높이를 확인한다. → tall보다 높지 않다면 높을 때까지 내용물을 pop한다. 이렇게 계속 pop을 하다가 높은 것이 나오면 (2-1)의 과정을 밟게 되지만, 아닐 경우 스택이 빈다. → 빌 경우 0을 출력 (2)

(2) stack 확인, 비어있다면 0 출력

 

(3) 1, 2번 과정을 마치면 무조건 stack에 tall과 위치를 push해준다. 이 때, stack 안에는 tall보다 높은 빌딩이 있거나 아예 없다.(tall보다 높지 않으면 무조건 pop하는 과정을 거쳤기 때문이다. tall보다 높은 빌딩도 stack에 자신보다 높지 않은 빌딩들은 무조건 출력해주었다.)

 

위 과정을 매 탑 높이가 입력될 때마다 반복한다.

 

 

 

package boj;

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

class Tower {
	long height;
	int position;

	public Tower(long height, int position) {
		this.height = height;
		this.position = position;
	}

}

public class Boj2493 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int num = Integer.parseInt(br.readLine());
		Stack<Tower> stack = new Stack<Tower>();
		String[] towers = br.readLine().split("\\s");
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=num; i++) {
			int tall = Integer.parseInt(towers[i-1]);
			while(!stack.isEmpty()) {
				if(stack.peek().height >= tall) {
					sb.append(stack.peek().position);
					sb.append(" ");
					break;
				}
				stack.pop();
			}
			if(stack.isEmpty()) sb.append("0 ");
			stack.push(new Tower(tall, i));
		}
		System.out.println(sb);
		br.close();
	}

}