[PS] BOJ2493 탑 ( Stack ) with JAVA

2493번: 탑

 

◎ 문제해결

 

스택을 이용하면 쉽게 풀리는 문제이다.

스택을 처음에 발상했지만 시간복잡도에 걸릴 것이라 판단했었다. 그런데 다시 생각해보니 그렇지 않았다.

 

6   9   5   7   4

 

왼쪽부터 하나씩 포인터를 이동하면서 Stack의 Top과 비교한다. Top이 작으면 POP한다. 

 

스택에 더이상 값이 없으면 0을 출력하고

Top에 자신보다 크거나 같은 수가 있으면 출력한다.

 

그리고 자신의 인덱스를 스택에 PUSH 한다. 

스택에는 포인터 이전의 수가 모두 들어가 있지 않고 POP 되기에 시간복잡도에 걸리지 않는다.

 

◎ 코드

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

//BOJ2493 탑
public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=1;i<=n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        for(int i=1;i<=n;i++){
            while(!stack.isEmpty()){
                int top = stack.peek();
                if( arr[i] > arr[top] ) stack.pop();
                else {
                    stack.push(i);
                    sb.append(top).append(" ");
                    break;
                }
            }

            if(stack.isEmpty()){
                sb.append(0).append(" ");
                stack.push(i);
            }
        }

        System.out.println(sb.toString());
    }
}