[BaekJoon] 백준 2493번 _ 탑 for JAVA

 

https://www.acmicpc.net/problem/2493

2493번: 탑

 

문제

 

---

 

스택을 활용한 문제이다.

 

6 9 5 7 4 의 높이를 가진 탑일 때

 

4의 높이에서 레이저를 쏜다면 7에, 7의 높이에서 레이저를 쏜다면 9에 맞을 것이다.

 

 

해당 위치에서 왼쪽 방향으로 레이저를 쐈을 때 몇 번째 건물에 맞는지 구하는 문제이다.

 

 

여기서 알아야 할 것은 6 다음에 9를 스택에 넣었을 때, 다음 건물들은 6에 레이저를 절대 맞출 수 없다는 것이다.

 

그래서 스택에 첫 번째 건물부터 넣으면서 stack의 제일 위 건물의 높이가 현재 건물의 높이보다 작다면 pop 해주면 된다.

 

 

모두 pop 해주고 남은 건물에 레이저가 닿게 될 것이므로, 해당 건물의 순서를 담아주면 된다.

 

 

그래서 건물의 높이와 건물의 순서(몇 번째 건물인지)를 stack에 int[]로 넣어주었다~!

 

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		Stack<int[]> stack = new Stack<>(); // 건물의 높이, 건물의 순서
		
		for(int i=1; i<=N; i++) {
			int in = Integer.parseInt(st.nextToken());
			
			while(!stack.isEmpty() && stack.peek()[0] < in) {
				stack.pop();
			}
			
			if(stack.isEmpty()) {
				sb.append("0").append(" ");
			} else {
				sb.append(stack.peek()[1]).append(" ");
			}
			stack.add(new int[] {in, i});
		}
		
		System.out.println(sb.toString());
	}
}

 

성능