BOJ 2493번: 탑

문제

문제 바로가기> BOJ 2493번: 탑

2493번: 탑

 

풀이

stack을 이용해서 푸는 문제다! 

이전에 비슷한 문제를 풀어봤었는데,

처음 접했으면, stack으로 풀어야지라고 생각하지 못했을 것 같기도 하다.

 

현재 빌딩의 높이가 입력으로 들어올 때, 총 3가지의 경우가 있다.

 

1. stack이 비어 있는 경우

   : 레이저를 수신할 탑이 없다. 따라서, 0을 출력한다.

 

2. stack의 top이 현재 빌딩의 높이보다 큰 경우

   : stack의 top이 바로 레이저를 수신할 탑이다!

 

3. stack의 top이 현재 빌딩의 높이보다 작은 경우

   : 레이저를 수신할 탑을 찾을 때 까지 pop 해준다. 

     이 때, 스택이 비게 되는 경우, 레이저를 수신할 탑이 없는 것이므로 0을 출력한다.

 

+ 매 과정에서 현재 빌딩의 번호와, 높이를 stack에 push 해준다!

 

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

public class Main {
	
	static StringBuilder sb = new StringBuilder();
	static int N;

	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지
		// 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력
		
		int height=0;
		Deque<int[]> stack = new ArrayDeque<>(); //num, height
		for(int i=1; i<=N; i++) {
			height = Integer.parseInt(st.nextToken());
			if(stack.isEmpty()) sb.append(0 + " ");
			else if(stack.peekLast()[1] > height) sb.append(stack.peekLast()[0] + " ");
			else {
				while(!stack.isEmpty() && stack.peekLast()[1] <= height) stack.pollLast();
				if(stack.isEmpty()) sb.append(0 + " ");
				else sb.append(stack.peekLast()[0] + " ");
			}
			stack.offer(new int[] {i, height});
		}
		System.out.println(sb.toString());
	}
}