[백준] 2493번 탑 java

www.acmicpc.net/problem/2493

2493번: 탑

문제 풀이:

문제는 자신의 왼쪽에서 가장 가까운 큰 탑의 번호를 출력해야합니다.

먼저 인덱스와 탑의 높이를 저장하기 위한 클래스 Pair를 생성해줍니다.

탑의 높이를 하나씩 입력 받으면서 스택을 이용합니다.

1. 스택이 비어있으면, 탑이 존재하지 않으므로 0을 출력합니다. 그리고 입력받은 인덱스와 탑의 높이를 스택에 삽입합니다.

2. 스택이 비어있지 않으면, 스택이 비어있을 때까지 반복을 합니다.

2.1 스택의 top 부분의 번호가 입력 받은 번호보다 작다면 (탑에 수신이 안되므로), 스택에서 pop을 해줍니다.

2.2 스택의 top 부분의 번호가 입력 받은 번호보다 크거나 같다면 (탑에 수신이 되므로), 탑 번호를 출력해주고, 스택에 입력 받은 번호를 삽입해줍니다. 이 때, break문을 통해 반복문을 빠져나가줍니다. 

주의할 점은 Scanner는 메모리초과가 나므로 BufferedReader를 통해 입력을 받아줍니다.

 

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

public class Main{
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		Stack<Pair> stack = new Stack();
		
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());

			while(!stack.isEmpty()) {
				if(stack.peek().y < num) {
					stack.pop();
				}
				else {
					System.out.print(stack.peek().x+1+" ");
					stack.add(new Pair(i,num));
					break;
				}
				
			}

			if(stack.isEmpty()) {
				System.out.print("0 ");
				stack.add(new Pair(i,num));
			}
		}
	}
}
class Pair{
	int x;
	int y;
	Pair(int x, int y){
		this.x = x;
		this.y = y;
	}
}