[백준] 22866: 탑 보기 - JAVA

in Algorithm on 자료 구조

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

풀이

N개의 건물의 높이가 주어진다.

각 건물의 옥상에서 양 옆을 볼 때, 현재있는 건물의 높이보다 큰 건물만 볼수있고,

큰 건물로 가려지면 볼 수 없다.

스택을 이용해 저장하면서 현재 빌딩보다 낮으면 없애주는 식으로 구현했다.

왼쪽부터, 오른쪽부터 두번에 걸쳐 스택에 저장하는 과정을 거쳤다.

왼쪽부터 진행할 때는 현재 건물의 왼쪽을 본다는 것이고 오른쪽부터 진행하면 오른쪽을 본다는 것이다.

메모리: 34648KB

시간: 656ms

언어: Java 11

코드

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

public class Main {
    static class Building {
        int idx;
        int height;

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

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

        int[] near = new int[N + 1];
        int[] cnt = new int[N + 1];

        Stack<Building> stack = new Stack<>();
        for (int i = 1; i < N + 1; i++) {
            while (!stack.isEmpty() && stack.peek().height <= arr[i].height) {
                stack.pop();
            }
            cnt[i] += stack.size();

            if (!stack.isEmpty()) {
                near[i] = stack.peek().idx;
            }

            stack.push(arr[i]);
        }

        stack = new Stack<>();
        for (int i = N; i >= 1; i--) {
            while (!stack.isEmpty() && stack.peek().height <= arr[i].height) {
                stack.pop();
            }
            cnt[i] += stack.size();

            if (!stack.isEmpty()) {
                if (near[i] != 0) {
                    if (i - near[i] > stack.peek().idx - i) {
                        near[i] = stack.peek().idx;
                    }
                } else {
                    near[i] = stack.peek().idx;
                }
            }

            stack.push(arr[i]);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N + 1; i++) {
            if (cnt[i] != 0) {
                sb.append(cnt[i]).append(" ").append(near[i]).append("\n");
            } else {
                sb.append(cnt[i]).append("\n");
            }
        }

        System.out.println(sb);
    }

}