[백준]2493: 탑 - JAVA

[백준]2493: 탑

www.acmicpc.net/problem/2493

2493번: 탑

풀이

자료구조 관련 문제로 볼 수 있을 것 같다. 문제는 어렵지 않으나 메모리, 시간 초과가 발생하지 않도록 적절한 자료구조를 사용해 주어야 한다.

 

우선 문제의 조건을 분석해 보면, 탑의 높이를 입력 받고 나서 레이저를 자신 보다 앞의 인덱스의 탑에만 송신한다. 즉, 탑을 미리 입력을 받지 않고 입력 받으면서 이미 입력 받은 값들 하고와 비교하여도 충분히 문제를 풀 수 있다는 것이다.

 

이를 이용하여 Stack을 사용해서 문제를 풀었다. 입력 받은 높이 값이 현재 높이값 보다 낮다면 어짜피 해당 탑에는 레이저가 닿을 수 없으므로 pop을 해주었다. 또한 현재 스택이 비어있다면 레이저가 닿을 수 있는 탑이 없다는 의미이므로 0을 출력해 주었다.

 

문제의 예제 입력을 해결하는 과정을 그림으로 나타내면 아래와 같당.

 

또한, Scanner를 사용하면 메모리초과가 발생한다. 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        Stack<int[]> stack = new Stack<>();
        for(int i = 1; i <= n; i++) {
            int top = Integer.parseInt(st.nextToken());
            while(!stack.isEmpty()) {
                if(stack.peek()[1] >= top) {
                    System.out.print(stack.peek()[0] + " ");
                    break;
                }
                stack.pop();
            }
            if(stack.isEmpty()) {
                System.out.print("0 ");
            }
            stack.push(new int[] {i, top}); 
        }
    }
}