백준 22866번 : 탑보기(자바)

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

문제

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

 i번째 건물 기준으로 i - 1, i - 2, ..., 1번째 건물은 왼쪽에, i + 1, i + 2, ..., N번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.

현재 있는 건물의 높이가 L이라고 가정하면 높이가 L보다 큰 곳의 건물만 볼 수 있다.

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

번호	1	2	3	4	5	6	7	8
높이	3	7	1	6	3	5	1	7
보이는 건물 번호	2	x	2, 4, 8	2, 8	2,4,6,8	2,4,8	2,4,6,8	x

각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.

---

입력

첫번째 줄에 건물의 개수 N이 주어진다.

두번째 줄에는 N개의 건물 높이가 공백으로 구분되어 주어진다.

---

출력

 i(1≤i≤N)번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면 i번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

🔵풀이

스택으로 푸는 것을 바로 떠올릴 수 있었다. 비슷한 유형의 스택 문제가 많아 그랬다. 스택으로 한 방향을 검사할 수 있기 때문에 정방향으로 볼 수 있는 건물의 개수를 구한 후 배열을 역전시켜 다시 역방향을 볼 수 있는 건물의 개수를 구했다. 그런데 볼 수 있는 가장 가까운 건물을 구하는 것이 까다로웠다. 그냥 빡구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.EmptyStackException;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

class Main {
  static int N;
  static List<Integer> arr;
  static int[] near;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.valueOf(br.readLine());
    arr = new ArrayList<>();
    near = new int[N];
    int[] merge = new int[N];
    StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
    StringBuffer stringBuffer = new StringBuffer();

    for (int i=0; i<N; i++){
      arr.add(Integer.valueOf(stringTokenizer.nextToken()));
    }


    int[] forward = singleDirection(true);
    Collections.reverse(arr);
    int[] backward = singleDirection(false);

    for(int i=0; i<N; i++){
      merge[i] = forward[i]+backward[N-1-i];
    }


    for(int i=0; i<N; i++){
      if (merge[i]!=0){
        stringBuffer.append(merge[i]+" "+near[i]+"\n");
      }else stringBuffer.append(0+"\n");
    }
    System.out.println(stringBuffer);
  }
  static int[] singleDirection(boolean flag){

    Stack<Integer> stack  = new Stack<>();
    stack.add(0);
    int[] store = new int[N];

    for (int i=1; i<N; i++){
      if (arr.get(stack.peek())>arr.get(i)){
        store[i] = store[stack.peek()]+1;
        if (store[i]!=0){
          if (flag&&near[i]==0) {
            near[i] = stack.peek()+1;
          }else if ((!flag&&near[N-i-1]==0)||(!flag&&i-stack.peek()<N-i-near[N-i-1])){
            near[N-i-1] = N-stack.peek();
          }
        }
        stack.add(i);
      }
      else {
        while (!stack.isEmpty()&&arr.get(stack.peek())<=arr.get(i)){
          stack.pop();
        }
        try {
          store[i] = store[stack.peek()]+1;
        }catch (EmptyStackException e ){
          store[i] = 0;
        }finally {
          if (store[i]!=0){
            if (flag&&near[i]==0) {
              near[i] = stack.peek()+1;
            }else if ((!flag&&near[N-i-1]==0)||(!flag&&i-stack.peek()<N-i-near[N-i-1])){
              near[N-i-1] = N-stack.peek();
            }
          }
          stack.add(i);
        }
      }
    }
    return store;
  }
}