[Java] 백준 22866 탑 보기

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

난이도

골드3

문제

일직선으로 다양한 높이의 건물이 총
$N$개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다.

$i$번째 건물 기준으로 $i - 1$, $i - 2$, ...,
$1$번째 건물은 왼쪽에, $i + 1$, $i + 2$, ...,
$N$번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.

현재 있는 건물의 높이가
$L$이라고 가정하면 높이가
$L$보다 큰 곳의 건물만 볼 수 있다.

바라보는 방향으로 높이가
$L$인 건물 뒤에 높이가
$L$이하인 건물이 있다면 가려져서 보이지 않는다.

각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.

입력

첫번째 줄에 건물의 개수 $N$이 주어진다.

두번째 줄에는 $N$개의 건물 높이가 공백으로 구분되어 주어진다.

출력

$i(1 \le i \le N)$번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면
$i$번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

내 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] height = new int[N + 1];
        int[] count = new int[N + 1];
        int[] closest = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            height[i] = Integer.parseInt(st.nextToken());
            closest[i] = -1;
        }

        Stack<Integer> stack = new Stack<>();

        // 왼쪽 → 오른쪽
        for (int i = 1; i <= N; i++) {
            while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
                stack.pop();
            }
            count[i] = stack.size();
            if (count[i] > 0) {
                closest[i] = stack.peek();
            }
            stack.push(i);
        }

        stack = new Stack<>();

        // 오른쪽 → 왼쪽
        for (int i = N; i > 0; i--) {
            while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
                stack.pop();
            }
            int s = stack.size();
            count[i] += s;
            if (s > 0) {
                if (closest[i] == -1 || (stack.peek() - i < i - closest[i])) {
                    closest[i] = stack.peek();
                }
            }
            stack.push(i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(count[i]);
            if (count[i] > 0) {
                sb.append(" ").append(closest[i]);
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}