[백준] 22866 탑보기 java 문제풀이

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

문제 이해

• 일직선 상의 N개의 건물에서 각 건물이 볼 수 있는 다른 건물의 수와 가장 가까운 건물을 찾음
• 각 건물은 자신보다 높은 건물만 볼 수 있음
• 두 건물 사이에 다른 건물이 있을 경우, 어느 하나라도 시야를 가리면 볼 수 없음

문제 풀이

데이터

static class Building{
    int idx, height;
}
int[] count;
int[] closet;
Stack<Building> stack;

건물 처리
현재 건물보다 낮거나 같은 건물 제거, 볼 수 있는 건물 개수 세기, 가장 가까운 건물 선택

단계별 자세한 동작 설명
스택 정리 과정

• 목적: 현재 건물에서 볼 수 없는 건물들을 스택에서 제거
• 조건: 현재 건물보다 낮거나 같은 높이의 건물은 제거
• 이유: 이러한 건물들은 현재 건물 뒤에 있는 건물들에게 가려지기 때문
• 결과: 스택에는 현재 건물보다 높은 건물들만 남음

볼 수 있는 건물 수 계산

• 방법: 스택에 남아있는 건물 수를 현재 건물의 count에 더함
• 의미: 스택에 남아있는 모든 건물은 현재 건물에서 볼 수 있는 건물들
• 누적: 왼쪽 방향과 오른쪽 방향 각각 처리하여 결과를 합산

가장 가까운 건물 갱신

• 기준: 거리가 가장 가까운 건물 선택
• 동일 거리: 건물 번호가 작은 것 선택
• 계산 방법: 현재 건물과 스택 맨 위 건물 간의 거리 계산
• 비교: 기존에 저장된 가장 가까운 건물과 비교하여 갱신

스택에 현재 건물 추가

• 목적: 이후 건물들이 현재 건물을 볼 수 있는지 판단
• 의미: 현재 건물이 이후 건물들의 시야를 가릴 수 있음

스택을 사용하는 이유

• 효율성: 각 건물은 최대 한 번씩 스택에 들어가고 나옴 (O(N) 시간 복잡도)
• 가시성 유지: 스택은 현재 건물에서 볼 수 있는 건물들만 유지
• 자동 정렬: 스택 내 건물들은 항상 현재 건물보다 높은 순서로 유지됨
• 가장 가까운 건물 쉽게 찾기: 스택 맨 위 건물이 가장 가까운 건물

시간 및 공간 복잡도

• 시간 복잡도: O(N) - 각 건물을 한 번씩만 처리
• 공간 복잡도: O(N) - 건물 정보와 결과 저장에 필요한 공간

이 풀이는 스택의 특성을 활용하여 단순 풀이시 O(N²) 접근법을 O(N)으로 최적화

import java.io.*;
import java.util.*;
public class Main {
    static 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());
        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()));
        }
        int[] count = new int[N + 1];
        int[] closest = new int[N + 1];
        Arrays.fill(closest, Integer.MAX_VALUE);
        Stack<Building> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            processBuilding(stack, count, closest, buildings[i]);
        }
        stack.clear();
        for (int i = N - 1; i >= 0; i--) {
            processBuilding(stack, count, closest, buildings[i]);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(count[i]);
            if (count[i] > 0) {
                sb.append(" ").append(closest[i]);
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
    // 건물 처리
    private static void processBuilding(Stack<Building> stack, int[] count, int[] closest, Building current) {
        while (!stack.isEmpty() && stack.peek().height <= current.height) {
            stack.pop();
        }
        count[current.idx] += stack.size();
        if (!stack.isEmpty()) {
            int distance = Math.abs(stack.peek().idx - current.idx);
            int prevDistance = Math.abs(closest[current.idx] - current.idx);
            if (distance < prevDistance) {
                closest[current.idx] = stack.peek().idx;
            } else if (distance == prevDistance) {
                closest[current.idx] = Math.min(closest[current.idx], stack.peek().idx);
            }
        }
        stack.push(current);
    }
}