[BOJ/2493/Java] 탑

1. 문제 이해

각 타워가 오른쪽에서 왼쪽으로 레이저를 쏠 때, 가장 먼저 닿는 탑의 번호를 출력하는 문제

2. 문제 분석

왼쪽에서 오른쪽으로 진행하면서 스택을 관리한다

• 현재 index의 탑의 높이를 h라고 할 때
• stack.isEmpty()
  • 현재 타워의 레이저는 어느 탑에도 닿지 않는다.
• stack.peek().높이 < h
  • 마찬가지로 현재 타워의 레이저는 어느 탑에도 닿지 않는다.
  • 이후 h보다 작은 타워의 레이저는 모두 index의 탑에 닿게 될 테니, stack의 최상단 값을 현재 탑으로 갱신
• stack.peek().높이 > h
  • 현재 타워의 레이저는 stack.peek()인 탑에 닿는다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.stream.Stream;

import static java.lang.Integer.parseInt;
import static java.lang.System.in;

public class Main {
    static int[] heights;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));

        int n = st(br.readLine());

        heights = Stream.of(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();


        Stack<Tower> towerStack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int h = heights[i];
            while(!towerStack.isEmpty() && towerStack.peek().height < h) {
                towerStack.pop();
            }

            if (towerStack.isEmpty()) {
                sb.append("0 ");
            } else {
                sb.append(towerStack.peek().index + " ");
            }
            towerStack.add(new Tower(h, i + 1));
        }
        System.out.println(sb.toString());
    }

    public static int st(String str) {
        return parseInt(str);
    }

    static class Tower {
        int height;
        int index;

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