[백준] 2493 탑 [java]

문제

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

시간초과

위 그림으로 이해하면 될 것 같다.
쉽게 생각하면 그냥 뒤에서부터 2중 반복문을 돌면서 본인보다 큰 탑이 있다면 크 탑의 인덱스를 저장하고, 없다면 0을 저장하는 식으로 풀면 될 것이라고 생각된다.
하지만, 탑의 수가 최대 50만으로,
만약 탑이 50만개 있고, 뒤로 갈수록 탑의 높이가 높아지면 반복 횟수는 50만X50만이 되고 시간복잡도는 O(n^2)이 되므로 무조건 시간초과가 난다.

풀이법

스택을 이용한다.
1. 타워의 높이와 타워 번호(인덱스)를 필드로 갖는 클래스는 생성한다.
2. 현재 탐색중인 타워와 스택 top에 있는 타워의 높이를 비교하여 현재 타워 높이보다 낮으면 제거한다.
3-1. 현재 타워보다 높은 타워가 top에 있으면 해당 타워의 타워번호를 정답 배열에 저장한다.
3-2. 만약, 스택이 비어있으면 현재 탐색중인 타워보다 높은 타워가 없는 것이므로 정답 배열에 0을 저장한다.
5. 현재 타워를 스택에 push한다.
6. 마지막까지 반복한다.
** 2~5를 요약하자면, 타워를 맨 앞부터 탐색하면서 현재 타워보다 낮은 타워는 스택에서 지우고, 현재 타워를 넣는다고 보면 된다. 그러면, 자연스럽게 스택에는 쓸모없는 타워가 남지 않게 된다.

3,4,5번째 타워 입장에서 보면, 2번 타워에 레이저가 갈 수 있기 때문에 1번은 쓸모 없는 타워이다.
5번 타워 입장에서 보면, 4번 타워에 레이저가 갈 수 있기 때문에 3번은 쓸모 없는 타워이다.

코드

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

// 배열 첫번째부터 1,2,3,4... 본인보다 왼쪽에 있는 수 중 가장 가까운 수의 자리
// 스택에 자기보다 작은거 있으면 빼다가 자기보다 큰거 나오면 그 타워의 번호 정답에 저장하고 본인 push
public class Main {

    public static class Tower{
        int num;
        int height;

        public Tower(int num, int height){
            this.num = num;
            this.height = height;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int[] arr = new int[size + 1];
        int[] ans = new int[size + 1];
        for(int i = 1; i <= size; i++){
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        Stack<Tower> stack = new Stack<>();
        stack.push(new Tower(1, arr[1]));
        ans[1] = 0;

        for(int i = 2; i <= size; i++){

            while(!stack.isEmpty() && stack.peek().height < arr[i]){        //현재 스택 탑이 현재 탑보다 작으면
                stack.pop();
            }
            if(!stack.isEmpty()){
                ans[i] = stack.peek().num;
            }
            else{
                ans[i] = 0;
            }
            stack.push(new Tower(i, arr[i]));
        }

        for(int i = 1; i <= size; i++){
            System.out.print(ans[i] + " ");
        }

    }

}