문제 링크

반년 전에 풀었던 문제를 다시 풀어보았다.

풀이

Stack을 선언하고, 각 탑을 순서대로 스택에 넣는다.
현재 탑을 스택에 넣기 전에, 스택에 쌓인 탑 중 현재 탑보다 낮은 높이의 탑들은 모두 pop()하여 제거한다.

낮은 탑들을 제거하는 이유는, 이후에 더 높은 탑이 추가되더라도 이미 현재 탑보다 낮은 탑은 수신 신호를 받을 수 없기 때문이다.

낮은 탑들을 모두 제거한 뒤, 만약 스택이 비어 있다면 현재 탑보다 높은 탑이 하나도 없다는 뜻이므로 0을 출력한다.

스택에 요소가 남아 있다면, 맨 위의 탑(peek())이 현재 탑보다 높아서 신호를 수신할 수 있는 탑이므로, 해당 탑의 인덱스(idx)를 출력한다.

모든 처리가 끝난 후에는 현재 탑을 스택에 push하여 이후 탑들의 수신 가능성을 판단할 수 있도록 한다.

코드

package BOJ;

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

public class sol2493_2 {
    static int n;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        Stack<Tower> towerStack = new Stack<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int height = Integer.parseInt(st.nextToken());
            while (!towerStack.isEmpty() && towerStack.peek().height < height) {
                towerStack.pop();
            }
            if (towerStack.isEmpty()) {
                sb.append("0 ");
            } else {
                sb.append(towerStack.peek().idx).append(" ");
            }
            towerStack.push(new Tower(height, i + 1));
        }

        System.out.println(sb);

    }

    public static class Tower {
        int height;
        int idx;

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