22866 탑보기 [JAVA]

문제 분석

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

N개의 배열에 대해 i번째 원소의 왼쪽 (0~i-1)과 오른쪽 (i+1 ~ n-1) 에 대해서 각각

i번째 원소의 값보다 큰 원소를 i번째 원소가 볼 수 있다.

왼쪽을 쳐다보는 기준 a<b<i 일때, b원소의 값이 a보다 작아야 i가 a,b를 볼 수 있다.

 

0번째 빌딩부터 오른쪽으로

그리고 마지막 빌딩부터 0쪽 방향, 즉 왼쪽으로 2번에 걸쳐서 탐색하며 문제를 해결했다.

 

스택에 순차적으로 빌딩을 삽입하고

i번째 빌딩보다 높은 빌딩만 남겨둔다면

결국 스택의 크기가 i번째 빌딩이 볼 수 있는 빌딩의 수가 되고

스택의 peek의 값이 가장 최근에 삽입된, i와 가장 가까운 볼 수 있는 빌딩이 된다.

 

이를 왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽으로 한 번씩 탐색하면 i의 입장에서 볼 수 있는 빌딩의 수와 가장 가까운 index를 알 수 있게 된다.

 

코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Building[] buildings = new Building[n];
        for (int i = 0; i < n; i++) {
            int height = sc.nextInt();
            buildings[i] = new Building(i, height);
        }

        Stack<Building> leftToRightStack = new Stack<>();
        Stack<Building> rightToLeftStack = new Stack<>();

        leftToRightStack.add(buildings[0]);

        for (int i = 1; i < n; i++) {
            while(!leftToRightStack.isEmpty() && leftToRightStack.peek().height <= buildings[i].height){
                leftToRightStack.pop();
            }

            if(!leftToRightStack.isEmpty()) {
                buildings[i].visibleBuildingCount += leftToRightStack.size();
                buildings[i].closestIdx = leftToRightStack.peek().idx;
            }
            leftToRightStack.add(buildings[i]);

        }

        rightToLeftStack.add(buildings[n-1]);

        for(int i = n-2; i>=0 ;i--){
            while (!rightToLeftStack.isEmpty() && rightToLeftStack.peek().height <= buildings[i].height){
                rightToLeftStack.pop();
            }

            if(!rightToLeftStack.isEmpty()) {
                buildings[i].visibleBuildingCount += rightToLeftStack.size();
                int formerDis = i - buildings[i].closestIdx;
                int newDis = rightToLeftStack.peek().idx - i;
                buildings[i].closestIdx = formerDis > newDis ? rightToLeftStack.peek().idx : buildings[i].closestIdx;
            }
            rightToLeftStack.add(buildings[i]);
        }

        for (int i = 0; i < n; i++) {
            if(buildings[i].visibleBuildingCount == 0){
                System.out.println("0");
            }else{
                System.out.println(buildings[i].visibleBuildingCount+" "+(buildings[i].closestIdx+1));
            }
        }


    }

    static class Building{
        int idx,height;
        int visibleBuildingCount;
        int closestIdx;

        public Building(int idx, int height){
            this.idx=  idx;
            this.height = height;
            visibleBuildingCount = 0;
            closestIdx = -111111;
        }
    }




}