백준 22866[자바] java 탑 보기

문제 링크: https://www.acmicpc.net/problem/22866

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번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

▶해설

Stack을 활용해서 푸는 문제입니다. 단 Stack을 두 번 사용해야 합니다. 

 

데이터 세팅

 

건물의 데이터 나타내는 클래스

class Building{
    int index;
    int height;

    public Building(int index, int height) {
        this.index = index;
        this.height = height;
    }
}

 

arr -> 건물들의 정보

indexAndGap -> 건물들의 Index와 Index 차이 값을 담는 배열(가장 큰 차이는 10만이므로 차이 값은 100001로 초기화)

cnt -> 보이는 건물의 수

Building[] arr = new Building[n+1];
int [][] indexAndGap = new int[n+1][2];
int [] cnt = new int[n+1];
for(int i=1; i<=n; i++){
    arr[i] = new Building(i, Integer.parseInt(s[i-1]));
    Arrays.fill(indexAndGap[i],100001);
}

 

 

1. 왼쪽에 보이는 건물의 개수를 센다.

Stack에 들어있는 건물 중에서 자신보다 작거나 같으면 보이지 않는 건물입니다. 따라서 자신보다 크거나, 비어있을 때까지 pop을 진행하고 남은 Stack의 size가 보이는 건물의 수입니다. 

while(!stack.isEmpty() && stack.peek().height<=arr[i].height){
    stack.pop();
}

cnt[i] += stack.size();

 

그 후 Stack이 비어있지 않다면 보이는 건물이 존재하는 것입니다. Index의 차이가 가장 적은 건물의 Index를 구하면 됩니다. 

if(!stack.isEmpty()){
    int gap = Math.abs(stack.peek().index-i);
    if(gap<indexAndGap[i][1]){ // Index 차이가 더 적다면 무조건 바꾼다. 
        indexAndGap[i][0] = stack.peek().index;
        indexAndGap[i][1] = gap;
    }
    // Index 차이는 같지만, 건물의 번호가 다를 경우 건물 번호만 바꾼다. 
    else if(gap == indexAndGap[i][1] && stack.peek().index<indexAndGap[i][0]){ 
        indexAndGap[i][0] = stack.peek().index;
    }
}

 

2. 오른쪽에 보이는 건물의 수를 센다

이렇게 왼쪽에 보이는 건물을 진행했으므로 동일하게 방법으로 순서를 반대로 해서 오른쪽에 보이는 건물을 진행하면 됩니다. 

for(int i=n; i>=1; i--){
    while(!stack.isEmpty() && stack.peek().height<=arr[i].height){
        stack.pop();
    }

    cnt[i] +=stack.size();

    if(!stack.isEmpty()){
        int gap = Math.abs(stack.peek().index-i);
        if(gap<indexAndGap[i][1]){
            indexAndGap[i][0] = stack.peek().index;
            indexAndGap[i][1] = gap;
        }
        else if(gap == indexAndGap[i][1] && stack.peek().index<indexAndGap[i][0]){
            indexAndGap[i][0] = stack.peek().index;
        }
    }
    stack.push(arr[i]);
}

 

전체 코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.lang.*;

class Building{
    int index;
    int height;

    public Building(int index, int height) {
        this.index = index;
        this.height = height;
    }
}

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());

        Stack<Building> stack = new Stack<>();
        String[] s = br.readLine().split(" ");


        Building[] arr = new Building[n+1];
        int [][] indexAndGap = new int[n+1][2];
        int [] cnt = new int[n+1];
        for(int i=1; i<=n; i++){
            arr[i] = new Building(i, Integer.parseInt(s[i-1]));
            Arrays.fill(indexAndGap[i],100001);
        }

        for(int i=1; i<=n; i++){
            while(!stack.isEmpty() && stack.peek().height<=arr[i].height){
                stack.pop();
            }

            cnt[i] += stack.size();

            if(!stack.isEmpty()){
                int gap = Math.abs(stack.peek().index-i);
                if(gap<indexAndGap[i][1]){
                    indexAndGap[i][0] = stack.peek().index;
                    indexAndGap[i][1] = gap;
                }
                else if(gap == indexAndGap[i][1] && stack.peek().index<indexAndGap[i][0]){
                    indexAndGap[i][0] = stack.peek().index;
                }
            }

            stack.push(arr[i]);
        }

        stack =new Stack<>();
        for(int i=n; i>=1; i--){
            while(!stack.isEmpty() && stack.peek().height<=arr[i].height){
                stack.pop();
            }

            cnt[i] +=stack.size();

            if(!stack.isEmpty()){
                int gap = Math.abs(stack.peek().index-i);
                if(gap<indexAndGap[i][1]){
                    indexAndGap[i][0] = stack.peek().index;
                    indexAndGap[i][1] = gap;
                }
                else if(gap == indexAndGap[i][1] && stack.peek().index<indexAndGap[i][0]){
                    indexAndGap[i][0] = stack.peek().index;
                }
            }
            stack.push(arr[i]);
        }

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=n; i++){
            if(cnt[i]==0){
                sb.append(0).append("\n");
            }
            else{
                sb.append(cnt[i]).append(" ").append(indexAndGap[i][0]).append("\n");
            }
        }
        System.out.println(sb.toString());
    }
}