[백준] 2493. 탑

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

2493번: 탑

특별한 알고리즘이 필요하지 않은 문제이다. 그런데 자료구조로 스택을 사용해야 한다!

 

주요 로직은 다음과 같다.

1. 스택이 비어있으면, 답은 0이고 현재 값을 스택에 push한다.
2. 그렇지 않으면, peek한 값과 현재 값을 비교한다.
   1. peek한 값이 더 크면, 답은 peek한 값의 인덱스이고 현재 값을 스택에 push한다.
   2. 그렇지 않으면, peek한 값을 pop하고 2번으로 돌아간다.

예제 1번의 경우를 생각해보자. 입력 값은 차례대로 6, 9, 5, 7, 4이다.

1. 현재 값이 6일 때
   1. 스택이 비어있으므로, 답은 0이고 6을 스택에 넣는다.
2. 현재 값이 9일 때
   1. 6이 9보다 작으므로, 6을 pop한다.
   2. 스택이 비어있으므로, 답은 0이고 9를 스택에 넣는다.
3. 현재 값이 5일 때
   1. 9가 5보다 크므로, 9의 인덱스인 2가 답이고 5를 스택에 넣는다.
4. 현재 값이 7일 때
   1. 5가 7보다 작으므로, 5를 pop한다.
   2. 9가 7보다 크므로, 9의 인덱스인 2가 답이고 7을 스택에 넣는다.
5. 현재 값이 4일 때,
   1. 7이 4보다 크므로, 7의 인덱스인 4가 답이고 4를 스택에 넣는다.

이렇게 하다 보면, 스택에는 제일 처음에 들어간 값이 가장 크며 나중에 들어온 값일수록 그 값이 작다. 즉, 스택을 그림으로 표현해서 생각하면, 스택의 아래로 갈수록 그 값이 크다는 것이다. 이 문제에서 스택을 이용해야 하는 이유는 다음과 같다. 현재 값과 특정 값을 비교할 때, 현재 값보다 작은 특정 값은 스택에 계속 저장해둘 필요가 없다. 따라서 우리는 더 작은 경우 그 값을 스택에서 pop 해줬었다. 만약 스택에 5, 3 순서로 들어가있고 현재 값이 4라면, 4보다 작은 3을 스택에 저장해둘 필요가 없다. 어차피 4 다음의 값들은 높이가 4인 탑에 수신하게 될 것이고 4보다 작은 3은 비교할 필요도 없고 그 전에 높이가 4인 탑에 부딪히기 때문이다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n;
    static int[] arr;
    static int[] answer;

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

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

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

        // 1. 스택이 비어있으면, 답은 0 + 현재 값 push
        // 2. 스택이 비어있지 않으면, peek한 값과 현재 값 비교
        // 2-1. peek한 값이 더 크면, 답은 peek한 값의 인덱스 + 현재 값 push
        // 2-2. 그렇지 않으면, peek한 값을 pop하고 2번으로

        Stack<Node> stack = new Stack<>();
        for (int i = 1; i <= n; i++) {
            int now = arr[i];
            if (stack.isEmpty()) {
                answer[i] = 0;
                stack.push(new Node(now, i));
            } else {
                while (true) {
                    if (stack.isEmpty()) {
                        answer[i] = 0;
                        stack.push(new Node(now, i));
                        break;
                    }
                    if (stack.peek().num > now) {
                        answer[i] = stack.peek().idx;
                        stack.push(new Node(now, i));
                        break;
                    } else {
                        stack.pop();
                    }
                }
            }
        }

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

    static class Node {
        int num, idx;

        public Node(int num, int idx) {
            this.num = num;
            this.idx = idx;
        }
    }
}