[Java] 백준 22866번 : 탑 보기

문제

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

22866번: 탑 보기

 

 

풀이과정

stack을 활용하여 왼->오, 오->왼으로 각각 순회하면서 자신의 왼쪽 혹은 오른쪽으로 옆면을 볼 수 있는 건물을 찾는다.stack에는 데이터가 내림차순으로 남게 하여, 자신보다 큰 건물의 수는 stack의 크기와 동일하게 하면 된다.따라서, 자신보다 작은 값은 모두 pop시키고, 남은 stack크기를 자신이 볼 수 있는 건물 수에 더해주면 된다. 이때, stack의 top에 있는 값이 자신 양 옆에서 볼 수 있는 건물 번호가 되므로, 왼쪽 혹은 오른쪽 중 어느 것이 더 가까운지만 체크한다.

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[] h = new int[N + 1];
        int[] cnt = new int[N + 1], near = new int[N + 1];
        Stack<Integer> stack;

        //init
        for(int i=1; i<=N; i++){
            h[i] = Integer.parseInt(st.nextToken());
            near[i] = -100_000;
        }

        //left
        stack = new Stack<>();
        for(int i=1; i<=N; i++){
            while(!stack.isEmpty() && h[stack.peek()] <= h[i]){
                stack.pop();
            }
            cnt[i] = stack.size();
            if(cnt[i] > 0) near[i] = stack.peek();
            stack.push(i);
        }

        //right
        stack = new Stack<>();
        for(int i=N; i>0; i--){
            while(!stack.isEmpty() && h[stack.peek()] <= h[i]){
                stack.pop();
            }
            int s = stack.size();
            cnt[i] += s;
            if(s > 0 && stack.peek()-i < i-near[i]) near[i] = stack.peek();
            stack.push(i);
        }

        //result
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=N; i++){
            sb.append(cnt[i]);
            if(cnt[i] > 0){
                sb.append(" ").append(near[i]);
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}