[백준] Q22866 탑 보기JAVA

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

22866번: 탑 보기

1. 문제의 유형 및 이해

스택

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

현재 건물 높이가 L이라고 할 때, 높이가 L보다 큰 건물만 볼 수 있고,

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

각 건물에서 볼 수 있는 건물들의 개수와, 가장 가까운 건물 위치를 출력하라.

 

어떤 기준 건물을 중심으로 '왼편'과 '오른편' 위치에 존재하는 볼 수 있는 건물들을 출력해야합니다.

현재 건물 위치 i보다 큰 위치에 있는 건물들에 대해 차례차례 커지는 값들 중 그 전 최대 값보다 큰 값들에 대해 볼 수 있습니다.

'그 전 최대 값보다 큰 값들 중 차례차례 커지는 값들'의 모음을 보면 알 수 있을 것 같습니다.

예를들어 3 7 1 6 3 5 1 7 이 있고 우리는 3번째 index에 있다고 생각해봅시다.

한쪽방향 >> 방향을 본다고 하면

6

6 3(6보다 작음-> 못봄)

6 5(6보다 작음 못봄)

6 1 (6보다 작음)

6 7  

이기 때문에 총 6과 7 두가지 건물을 볼 수 있겠습니다.

이러한 과정을 오른쪽, 왼쪽 두 방향으로 나누어 계산하였습니다.

2. 문제 접근 방법

먼저 (<-)왼쪽을 바라본다고 가정하면 차례차례 확인하기 위해서 가장 앞단의 3부터 보기 시작해야합니다.

그랬을 때 마지막 값에서 이미 쌓여온 큰 건물들을 확인할 수 있습니다.

이 때 우리는 가장 가까운 것을 먼저보아야합니다.

'가장 가까운 것을 먼저 본다?' -> '먼저 들어온 것은 나중에 본다' -> FILO Stack을 의미합니다.

stack을 활용해서 '차례차례 커지는 값들'을 구현하기 위해 이전의 값들 중 작은 값들은 현재 건물이 모두 가리게 됨으로 빼가면서 stack을 쌓아 나갑니다.

여기서 출력해야 하는 값 들 중 가장 가까운값을 출력해야하므로 이에 대한 정보들을 neighbor라는 배열에 담아 두었습니다. 기본적으로 stack에서 가장 먼저 보는 값이 자신이 볼 수 있는 가장 가까운 값이므로, 왼쪽으로 볼때와 오른쪽으로 볼때 두 상황에 따라 비교하여 기록해둡니다.

 

stack에서는 자신이 볼 수 있는 건물들을 찾기 위해 현재 자신보다 같거나 작은 건물들을 모두 pop해줍니다.

이후 스택에 남아있는 건물들은 모두 볼 수 있는 건물들이기 때문에 size값을 갱신하고 자신을 push하여 다음 건물이 볼 수 있도록 넣어줍니다.

 

해당 과정을 왼쪽, 오른쪽 두번 나누어 진행하면 해결할 수 있었습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
/**
 * @문제번호 : Q22866
 * @문제이름 : 탑 보기
 * @난이도 : Gold IV
 * @date : 2022-03-23 오후 5:39
 * @author : pcrmcw0486
 * @문제이해
 * N개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있을까
 * i기준 i-1 i-2 왼쪽 i+1 i+2는 오른쪽
 * 건물 높이 L이라면 높이가 L보다 큰 곳의 건물만 볼 수 있는데,,
 * L건물 뒤에 높이 L이하면 안보인다.
 * 각 건물에서 볼 수 있는 건물들이 어떤 것이 있을까?
 *
 * @알고리즘
 * 스택
 * @접근방법

*/
public class Main {
    static private class Building{
        int idx, height;
        public Building(int idx, int height) {
            this.idx = idx;
            this.height = height;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Stack<Building> stack = new Stack<>();
        int[] size = new int[N + 1];
        int[] neighbor = new int[N + 1];
        Building[] buildings = new Building[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            buildings[i] = new Building(i + 1, Integer.parseInt(st.nextToken()));
        }
        Arrays.fill(neighbor, 222222);
        //왼쪽을 바라볼 떄
        for (int i = 0; i < N; i++) {
            findBuildings(stack, size, neighbor, buildings, i);
        }
        stack.clear();

        for (int i = N-1; i >=0; i--) {
            findBuildings(stack, size, neighbor, buildings, i);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N+1; i++) {
            sb.append(size[i]).append(" ");
            if (size[i] != 0) {
                sb.append(neighbor[i]);
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }

    private static void findBuildings(Stack<Building> stack, int[] size, int[] neighbor, Building[] buildings, int i) {
        Building b = buildings[i];
        while (!stack.isEmpty()) {
            if (stack.peek().height <= b.height) {
                stack.pop();
            }else
                break;
        }
        size[b.idx] += stack.size();
        if(!stack.isEmpty()){
            int cur =Math.abs(stack.peek().idx -b.idx);
            int prev = Math.abs(neighbor[b.idx]-b.idx);
            if( cur < prev ){
                neighbor[b.idx] = stack.peek().idx;
            } else if (prev == cur) {
                neighbor[b.idx] = Math.min(stack.peek().idx, neighbor[b.idx]);
            }
        }
        stack.push(b);
    }
}