이것저것 개발 블로그

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

문제)

풀이)

솔직히 이 문제는 아주 헤맸다. 뭔가 쉬운듯 아닌듯...

뭔가 스택을 쓰면 될 것 같은데.. 하면서 이것저것 하다가 결국 포기하고 다시 보며 노력한 문제!

맨 처음에는 스택이 비어있으므로 stringbuilder인 sb에는 0 추가, stack에 push 한다.

그 이후부터는 탑의 높이를 입력 받으면서 stack의 맨 꼭대기에 존재하는 높이와 비교를 한다.

만약 입력받은 높이가 더 높다면, pop 시키고, 스택의 다음 원소와 비교한다.

이때, 스택 원소의 높이가 더 높을 경우, sb에 해당 원소의 인덱스를 삽입하고, 입력받은 원소는 stack에 push한다.

이를 반복하면 끝!

코드의 이해를 돕기 위해 입력에 따른 stack의 상태를 표현해봤다. 

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

public class Main_BJ_2493_탑 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		Stack<int[]> stack = new Stack<>();
		StringBuilder sb = new StringBuilder();
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=n; i++) {
			//새로운 높이 입력받음 
			int Height = Integer.parseInt(st.nextToken());
			//스택에 비교대상이 있는지 
			while(!stack.empty()) {
				//스택의 꼭대기 높이와 새로운 높이 비교 
				if(stack.peek()[1] > Height) {
					//스택 꼭대기 높이가 더 높을 경우 꼭대기 인덱스 추가
					sb.append(stack.peek()[0] + " ");
					break;
				}
				// 새로운 높이가 더 높을 경우 pop 
				stack.pop();
			}//while
			
			//스택이 비어있을 때 
			if(stack.empty()) {
				sb.append("0 ");
			}
			
			// 스택에 인덱스와 높이 넣기 
			stack.push(new int[] {i, Height});
		}//for
		System.out.println(sb);
	}//main

}

처음에 Scanner를 썼는데, 메모리 초과가 나서 bufferedreader와 stringbuilder를 사용했다!