문제 접근

단순히 말해서, 타워를 기준으로 왼쪽에 있는 타워들 중 가장 먼저 해당 타워와 높이가 같거나 더 큰 타워를 찾으면 되는 문제다.

N이 50만 이였고, 시간제한은 1.5초였다. 즉, NlogN 문제였고, 나는 PriorityQueue를 사용해서 해결했다.
우선, 뒤에 타워부터 PQ에 넣기 시작했다.
원리는 다음과 같다.

• 우선, N번째 타워는 먼저 PQ에 넣는다.
• N-1번째 타워부터 1번재 타워까지 PQ에 넣어갈것임.
• 우선, 현재 타워의 높이 이하인 타워들을 모두 PQ에서 pop한다. 그리고 이 제거된 타워들의 결과는 현재 타워의 순번이 된다.
• 해당 타워를 PQ에 추가한다.
• 이 행위를 반복한다.

문제 풀이

import java.io.*;
import java.util.*;

class Main {
    static int N;
    static int[] numbers;
    static PriorityQueue<Tower> pq = new PriorityQueue<>((t1, t2) -> {
        return t1.h - t2.h;
    });
    static int[] result;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        numbers = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        if (N == 1) {
            System.out.println(0);
            return;
        }

        result = new int[N];
        result[0] = 0;
        StringBuilder sb = new StringBuilder();
        pq.add(new Tower(N - 1, numbers[N - 1]));

        for (int i = N - 2; i >= 0; i--) {
            int curH = numbers[i];
            while (!pq.isEmpty()) {
                Tower minTower = pq.poll();
                if (curH >= minTower.h) {
                    result[minTower.index] = i + 1;
                } else {
                    pq.add(minTower);
                    break;
                }
            }

            pq.add(new Tower(i, curH));
        }

        for (int i = 0; i < N; i++) {
            sb.append(result[i]).append(' ');
        }

        System.out.println(sb);
    }


}

class Tower {
    int index;
    int h;

    Tower(int index, int h) {
        this.index = index;
        this.h = h;
    }
}

스택으로 풀이

PQ로 해결하고나서, 이 문제의 유형을 찾아보니, 앞에서부터 스택으로 순회해도 풀리는 문제였다.

import java.io.*;
import java.util.*;

class Main {
    static int N;
    static int[] numbers;
    static Stack<Tower> stack = new Stack<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        numbers = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());

            while (!stack.isEmpty()) {
                Tower topTower = stack.peek();
                if (topTower.h >= numbers[i]) {
                    sb.append(topTower.index + 1).append(' ');
                    break;
                } else {
                    stack.pop();
                }
            }


            if (stack.isEmpty()) {
                sb.append(0).append(' ');
            }

            stack.add(new Tower(i, numbers[i]));
        }

        System.out.println(sb);
    }


}

class Tower {
    int index;
    int h;

    Tower(int index, int h) {
        this.index = index;
        this.h = h;
    }
}

이 문제의 조건을 잘 생각해보자.
i번째 타워의 바로 앞에 있던 i-1번째 타워보다 작은 1~i-2번째 타워들에 대한 정보는 필요 없다.
즉, 자기 바로 앞에 있는 타워의 정보와 그 앞 타워보다 큰 타워 정보 들만 유지하고 있으면 된다는 것임.
이것을 생각하고 코드를 짠다면, 스택이라는 개념이 쉽게 유도될 것 같다.