[BOJ][JAVA]2493 - 탑

문제 출처 : https://www.acmicpc.net/problem/2493

2493번: 탑

 

 

문제

 

 

 

설명

이 문제는 스택을 사용해서 푸는게 핵심입니다. 문제를 보고 바로 스택을 써야 한다는 감이 오지는 않았고, 수업에서 풀이를 듣고서야 그렇게 풀어야 함을 알게 되었습니다. 완전 탐색 등으로 나이브하게 풀면 바로 시간초과나 메모리 초과가 나기 때문에, 스택으로 풀어야만 하는 문제였습니다.

 

원리는 다음과 같습니다. 만약 스택의 top에 들어있는 탑의 높이가 현재 넣으려고 하는 탑의 높이보다 크다면, 현재 탑의 레이저 수신은 top의 탑이 할 것이므로 그 탑의 번호를 출력합니다.  만약 top이 더 작다면, 그 뒤에서 오는 모든 레이저들은 현재 넣으려는 탑이 모두 받을 것이므로, 사실상 top은 필요없게 되기 때문에 pop합니다.

이렇게 현재 넣으려는 탑과 스택 top과의 높이를 비교하는 과정이 끝난 다음에는, 동일하게 현재 탑을 push합니다. 뒤에 오는 탑들의 높이가 더 높을지, 낮을지 모르기 때문입니다.

 

여기서 주의해야 할 점은, push가 가장 마지막 단계에서 일어나야 한다는 점입니다. 즉, 상태 체크를 해서 해당 탑에 대한 결과를 프린트 한 다음에 push를 해야 합니다. 그렇게 하지 않으면, 예를 들어 문제에서 주어진 테스트 케이스에서 9에 대한 처리(0)가 누락되게 됩니다.

 

 

 

코드

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

public class BOJ2493_Tower {

	public static void main(String[] args) throws Exception {
		
		Stack<Tower> towers = new Stack<>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine()); //탑의 높이
		StringTokenizer st = new StringTokenizer(br.readLine()); //탑들의 높이를 토큰화
		
		
		for(int num=1; num<=N; num++) {
			int height = Integer.parseInt(st.nextToken());
			while(!towers.empty()) {//수신 가능할 때까지 stack의 데이터 조사
				if(height > towers.peek().height) { //바로 앞의 탑이 더 작으면, 앞으로도 그 탑은 계속 신호 못받기 때문에 팝
					towers.pop();
				} else {  //바로 앞의 탑에서 수신 가능
					sb.append(towers.peek().num + " ");
					break;
				}
			}
			
			if(towers.isEmpty()) { //앞에 받을 수 있는 탑이 없으므로
				sb.append("0" + " ");
			}
			//뒤에 나오는 탑들을 위해서
			towers.push(new Tower(num, height));
		}
		System.out.println(sb);
	}
}

class Tower{
	int num;
	int height;
	
	public Tower(int num, int height) {
		super();
		this.num = num;
		this.height = height;
	}
}