[Baekjoon] 탑 보기

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

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

public class Main {
    static StringBuilder answer = new StringBuilder();
    static int N;
    static int[] nearIdx, count, buildingHeights;

    public static void main(String[] args) throws IOException {
        init();
        sol();
        print();
    }

    static void sol() {
        Deque<Integer> s = new ArrayDeque<>();
        nearIdx = new int[N + 1];
        count = new int[N + 1];

        Arrays.fill(nearIdx, -1);

        for (int i = 1; i <= N; i++) {
            while (!s.isEmpty() && buildingHeights[s.peek()] <= buildingHeights[i]) {
                s.pop();
            }

            count[i] += s.size();

            if (!s.isEmpty()) {
                nearIdx[i] = s.peek();
            }

            s.push(i);
        }

        s.clear();

        for (int i = N; i >= 1; i--) {
            while (!s.isEmpty() && buildingHeights[s.peek()] <= buildingHeights[i]) {
                s.pop();
            }

            count[i] += s.size();

            if (!s.isEmpty()) {
                int rightNearIdx = s.peek();

                if (nearIdx[i] == -1 || Math.abs(rightNearIdx - i) < Math.abs(i - nearIdx[i])) {
                    nearIdx[i] = rightNearIdx;
                }
            }

            s.push(i);
        }

        for (int i = 1; i <= N; i++) {
            int cnt = count[i];

            answer.append(cnt);

            if (cnt >= 1) {
                answer.append(" ").append(nearIdx[i]);
            }

            answer.append("\n");
        }
    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        buildingHeights = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

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

    static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(answer));
        bw.close();
    }
}

주요 개념

• Stack

풀이 과정

• 첫 번째 빌딩에서 오른쪽을 바라본다고 했을 때, 두 번째 빌딩보다 높이가 작거나 같은 빌딩은 보이지 않는다.

  • 계산에 전혀 고려가 안되기 때문에 이전 빌딩 보다 높은 빌딩만 스택에 넣는다.

  • 첫 번째 빌딩에서 시작해서 마지막 빌딩까지 수행한다면 마지막 빌딩보다 높은 빌딩만 스택에 남게 된다.

• 반대로 마지막 빌딩에서 첫 번째 빌딩까지 탐색을 수행하여 각 빌딩에서 보이는 빌딩의 수를 구할 수 있게 된다.

• 이러한 알고리즘을 사용한 스택을 모노토닉 스택이라고 한다.