[백준] 22866번 : 탑 보기 Gold3(골드3) - JAVA[자바]

[Gold III] 탑 보기 - 22866

문제 링크

성능 요약

메모리: 41472 KB, 시간: 420 ms

분류

자료 구조, 스택

제출 일자

2024년 6월 14일 21:56:59

문제 설명

일직선으로 다양한 높이의 건물이 총 N$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) i번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

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

 

접근 방법

1. N이 최대 100,000임으로 시간복잡도는 선형인 O(N)으로 해결해야한다.

2. 스택이 적합하다고 판단
3. 스택 자료구조를 클래스로 만들어주고 각 인덱스와 높이를 저장하는 빌딩 클래스를 만들어놓는다.
4. 왼쪽과 오른쪽 스택을 다르게 생각하여 계산해주면 간단하게 구현 가능하다.

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 문제 : BOJ_22866_G3_탑보기
 * 메모리: 43856KB
 * 시간: 420ms
 * 접근 방법
 * 1. N이 최대 100,000임으로 시간복잡도는 선형인 O(N)으로 해결해야한다.
 * 2. 스택이 적합하다고 판단
 * 3. 스택 자료구조를 클래스로 만들어주고 각 인덱스와 높이를 저장하는 빌딩 클래스를 만들어놓는다.
 * 4. 왼쪽과 오른쪽 스택을 다르게 생각하여 계산해주면 간단하게 구현 가능하다.
 */
public class Main {
    // 스택
    static class Stack {
        Building[] element;
        int top;
        int size;

        public Stack(int size) {
            this.size = size;
            element = new Building[size];
            this.top = -1;
        }

        public void push(Building b) {
            if (top == size - 1) {
                return;
            }
            element[++top] = b;
        }

        public Building peek() {
            return element[top];
        }

        public Building pop() {
            return element[top--];
        }

        public boolean isEmpty() {
            return top == -1;
        }

        public int size() {
            return top + 1;
        }
    }

    // 각 인덱스와 높이를 가지는 빌딩 클래스
    static class Building {
        int idx;
        int 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());

        // Input
        int[] count = new int[N]; // 개수
        int[] mem = new int[N]; // 가까운 빌딩의 인덱스
        Building[] buildings = new Building[N]; // 각 높이를 빌딩에 저장하여 메모리를 절약
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            buildings[i] = new Building(i, Integer.parseInt(st.nextToken()));
            mem[i] = -1;
        }// Input End

        Stack left = new Stack(N);
        Stack right = new Stack(N);
        for (int i = 0; i < N; i++) {
            // 현재 왼쪽에 있는 건물 중 i번째 건물보다 낮다면 제거
            removeHeight(left, buildings, count, i);
            // 비어있지않다면 가장 가까운 건물 설정
            if (!left.isEmpty()) {
                setIdx(mem, i, left.peek().idx);
            }
            left.push(buildings[i]);

            // 오른쪽에서 i번째 있는 건물보다 작은 오른쪽 건물들 제거
            removeHeight(right, buildings, count, N - i - 1);
            if (!right.isEmpty()) {
                setIdx(mem, N - i - 1, right.peek().idx);
            }
            right.push(buildings[N - i - 1]);
        }
        // 연산 종료 후 남은 건물들의 높이 계산
        while (!left.isEmpty()) {
            Building b = left.pop();
            count[b.idx] += left.size();
        }

        while (!right.isEmpty()) {
            Building b = right.pop();
            count[b.idx] += right.size();
        }

        // OutPut
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(count[i]);
            if (count[i] != 0) {
                sb.append(' ').append(mem[i] + 1);
            }
            sb.append('\n');
        }
        System.out.println(sb);
        // OutPutEnd
    }

    // idx보다 작은 건물을 스택에서 제거
    private static void removeHeight(Stack stack, Building[] buildings, int[] count, int idx) {
        while (!stack.isEmpty() && stack.peek().height <= buildings[idx].height) {
            Building b = stack.pop();
            count[b.idx] = count[b.idx] + stack.size();
        }
    }

    private static void setIdx(int[] mem, int i, int idx) {
        if (mem[i] == -1) mem[i] = idx;
        int originDist = Math.abs(i - mem[i]);
        int newDist = Math.abs(i - idx);
        if (originDist > newDist || (originDist == newDist && idx < mem[i])) {
            mem[i] = idx;
        }
    }
}