[백준 22866번] 탑 보기 - java

문제 설명

1. 건물의 개수 N이 주어진다.

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

3. 각 건물은 자신의 높이보다 높은 건물들을 볼 수 있다.

4. 보고있는 방향으로는 앞에 있는 건물보다 높은 건물을만 볼 수 있다.

5. 오른쪽, 왼쪽 기준 볼 수 있는 모든 건물의 숫자랑 가장 가까운 건물 위치를 한줄씩 출력하면 된다.

풀이 과정

1. 구현

2. Stack을 사용해 주면 된다. 투포인터 비슷한가 싶었는데 전혀 아니었다.

3. 왼->오, 오->왼 하면서 Stack에 점점 높이가 낮아지면서 건물들을 저장한다.

4. 그러면서 현재 건물보다 높은것들만 있으면 그게 size, 그 중 가장 가까운 위치를 확인해주면 된다.

5. 모노토닉 스택에 대해서 알고 있으면 쉬울 수 있지만.. 나는 알고 있는데도 떠올리는데 시간이 오래 걸렸다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] height = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) height[i] = Integer.parseInt(st.nextToken());

        int[] canSeeCount = new int[N+1]; // 볼 수 있는 건물의 개수
        int[] nearIndex = new int[N+1]; // 가장 가까운 건물
        Arrays.fill(nearIndex, Integer.MAX_VALUE);  // 초기화

        // 지금 건물보다 높은 건물들을 보관하려는 stack
        Stack<Integer> stack = new Stack<>();

        // 왼쪽 -> 오른쪽
        for(int i=1; i<=N; i++) {
            // 현재 건물 왼쪽에 있는 애들 중 바로 앞에 있는게 지금보다 낮거나 같으면 안보임
            while(!stack.isEmpty() && height[stack.peek()] <= height[i]) {
                stack.pop();
            }
            canSeeCount[i] += stack.size(); // 나머지 건물들은 보인다.
            if(!stack.isEmpty()) { // 그 중 가장 가까운 건물 저장
                nearIndex[i] = stack.peek();
            }
            stack.push(i); // 지금 건물은 이제 이 stack에서 가장 낮은 건물이다.
        }

        stack.clear(); // 왼쪽 다 봤으면 걍 지움

        // 오른쪽 -> 왼쪽
        for(int i=N; i>=1; i--) {
            while(!stack.isEmpty() && height[stack.peek()] <= height[i]) {
                stack.pop();
            }
            canSeeCount[i] += stack.size(); // 반대쪽에서 보이는 건물 수 더하기
            if(!stack.isEmpty()) { // 가장 가까운 건물 확인, 가장 가까운 건물이 없으면 MAX_VALUE 였고 있으면 지금보다 먼 경우에만 갱신
                if(Math.abs(nearIndex[i] - i) > Math.abs(stack.peek() - i)) {
                    nearIndex[i] = stack.peek();
                }
            }
            stack.push(i);
        }

        for(int i=1; i<=N; i++) {
            if(canSeeCount[i] == 0) System.out.println(0);
            else System.out.println(canSeeCount[i] + " " + nearIndex[i]);
        }
    }
}