[JAVA][백준 2493] 탑 정답

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

2493번: 탑

정올의 탑 문제와도 비슷하다.

1. 백준 2493번 탑 문제

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성

2. 입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

3. 출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

4. 주의할 점

메모리초과, 시간초과. 

메모리초과와 시간초과를 면하기 위해서 BufferedReader와 StringBuilder를 사용하는 것이 관건이다. 처음에 스택 두개를 선언해서 더 복잡하게 만드는 뻘짓을 시도한 끝에 그냥 배열리스트를 만들기로 했다. ㅎ

증말 쉽지 않네 알고리즘! 아래는 백준 2493번의 정답코드이다.

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 {
		Stack<int []> stack=new Stack<>();
		int next;
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		StringBuilder sb=new StringBuilder();
		int N=Integer.parseInt(in.readLine());
		st=new StringTokenizer(in.readLine());
		
		for(int i=0;i<N;i++) {
			next=Integer.parseInt(st.nextToken());
			while(!stack.empty()&&stack.peek()[0]<=next) {
				stack.pop();
			}
			if(stack.size()==0) 
				sb.append(0).append(' ');
			else
				sb.append(stack.peek()[1]).append(' ');
			
			stack.push(new int[] {next,i+1});
			
		}
		System.out.println(sb.toString());

	}
}