[백준] 옥상 정원 꾸미기 - Java

문제 출처

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

문제

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

예제 입력 1

6
10
3
7
4
12
2

예제 출력 1

5

풀이 방법

• Stack을 이용하면서 풀이하였다.

-> 예제로 예를 들면..
1. 초기 건물은 stack에 넣어준다.
2. 그 다음 부터, 다음에 들어갈 값이 이전 값보다 크면 peek 기준에서 그 빌딩을 볼 수 없는 것, stack에서 (스택이 비거나, 더 큰 값이 등장하기 전...)조건을 만족하기 전까지 pop 해준다.
3. pop연산 완료시 result에 해당 스택의 크기를 더해주면 끝!(현재 idx이전 건물들을 포함하여 볼 수 있는 건물의 수가 저장되어있음)

예외 주의 사항!!

• 조건을 보면, N은 80000까지이고 입력될 수 있는 값은 10억 정도이다.
• 이 때, N을 10억으로 시작하여 -1 씩 감소한 형태로 빌딩들이 존재하면, 합의 값은 정수형 최대값인 약 21억을 쉽게 넘어가므로, result는 int형이 아닌 long형으로 선언해야 함!

풀이 코드

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

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<Integer> stack = new Stack<>();
        long result = 0;
        for(int i = 0; i < N; i++){
            int h = Integer.parseInt(br.readLine());

            while(!stack.isEmpty()){
                if(stack.peek() <= h){
                    stack.pop();
                }
                else {
                    break;
                }
            }

            result += stack.size();
            stack.push(h);
        }

        System.out.println(result);

    }
}

결과

회고

• 문제 풀면서 스택을 선입선출로 생각하는 멍청한 짓을 저질렀다.