백준 2493번 : 탑(Java)

 

2493번: 탑

---

[풀이]

 

- 스택을 이용한 자료구조 유형의 문제입니다.
- 단순히 for 반복문을 이용할 경우 시간 초과가 발생합니다.
- 그래서 스택에 있는 이전 값을 확인하며 대소비교를 하며 스택의 값을 삭제해야합니다.
  - 스택이 비어있다면 0을 출력합니다.
  - 스택의 최근 값이 새로 추가되는 값의 높이보다 클 경우, 인덱스를 출력하고 스택에 값을 추가합니다.
  - 만약, 최근 값이 새로 추가되는 값의 높이보다 작을 경우에는 이후 필요가 없기 때문에(어차피 새로 추가되는 값이 더 크기 때문에 작은 타워에 레이저가 오지 않습니다.) 스택에 pop()메소드를 해야 합니다.

---

[코드]

 

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

public class Main {

	static class Tower {

		int idx, height;

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Stack<Tower> stack = new Stack<>();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		for (int i = 1; i <= n; i++) {
			int tower = Integer.parseInt(st.nextToken());
			if (stack.isEmpty()) {
				System.out.print("0 ");
				stack.push(new Tower(i, tower));
			} else {
				while (true) {
					if (stack.isEmpty()) {
						System.out.print("0 ");
						stack.push(new Tower(i, tower));
						break;
					} else {
						if (stack.peek().height > tower) {
							System.out.print(stack.peek().idx + " ");
							stack.push(new Tower(i, tower));
							break;
						} else {
							stack.pop();
						}
					}
				}
			}
		}
	}
}