(6198) 옥상 정원 꾸미기 (Java)

문제

도시에는 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

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO November 2006 Contest > Silver 1번

잘못된 번역을 찾은 사람: jh05013
문제를 번역한 사람: skynet
문제의 오타를 찾은 사람: twinparadox, vl0612

알고리즘 분류

자료 구조
스택

Solution

1 런타임 에러 (EmptyStack)

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

public class Main {
    public static int n;
    public static int[] bd;
    public static Stack<Integer> sLeft;
    public static Stack<Integer> sRight;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        bd = new int[n];
        sLeft = new Stack<Integer>();
        sRight = new Stack<Integer>();

        // 빌딩 세팅
        for(int i = 0; i < n; i++) {
            bd[i] = Integer.parseInt(br.readLine());
        }

        // 맨 우측 빌딩부터 스택에 push
        for(int i = 1; i <= n; i++) {
            sRight.push(bd[n-i]);
        }

        bw.write(String.valueOf(countBm()));
        bw.flush();
        bw.close();
        br.close();

    }

    public static long countBm() {
        long cnt = 0;

        while(!sRight.isEmpty()) {
            // 최초 시작시 또는 새로 나온 빌딩이 이전에 나온 빌딩들보다 높은 경우 sLeft가 비워지게 되므로.
            if(sLeft.isEmpty()) sLeft.push(sRight.pop());

            // 지금 빌딩보다 오른쪽 빌딩이 낮은 경우
            // 현재 왼쪽에 위치하고 있는 빌딩들 전부보다 오른쪽 빌딩이 낮은 것이므로 스택에 담겨있는 빌딩 수만큼 cnt를 올려준다.
            // (주의) 오른쪽 빌딩을 sLeft에 담아주기 전에 카운트 먼저 해줘야함.
            if(sLeft.peek() > sRight.peek()) {
                cnt += sLeft.size();
                sLeft.push(sRight.pop());
            } else {
                sLeft.pop();
            }
        }

        return cnt;
    }
}

2

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

public class Main {
    public static int n;
    public static int[] bd;
    public static Stack<Integer> sLeft;
    public static Stack<Integer> sRight;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        bd = new int[n];
        sLeft = new Stack<Integer>();
        sRight = new Stack<Integer>();

        // 빌딩 세팅
        for(int i = 0; i < n; i++) {
            bd[i] = Integer.parseInt(br.readLine());
        }

        // 맨 우측 빌딩부터 스택에 push
        for(int i = 1; i <= n; i++) {
            sRight.push(bd[n-i]);
        }

        bw.write(String.valueOf(countBm()));
        bw.flush();
        bw.close();
        br.close();

    }

    public static long countBm() {
        long cnt = 0;

        while(!sRight.isEmpty()) {
            // 1. 최초 시작시 또는 새로 나온 빌딩이 이전에 나온 빌딩들보다 높은 경우 sLeft가 비워지게 되므로.
            if(sLeft.isEmpty()) sLeft.push(sRight.pop());

            // 2. sLeft로 원소를 하나 넘겼더니, sRight가 비어져버리는 경우(가장 오른쪽 빌딩이 가장 높은 경우)
            //    현재까지의 cnt를 return한다.
            if(sRight.isEmpty()) {
                return cnt;
            }

            // 지금 빌딩보다 오른쪽 빌딩이 낮은 경우
            // 현재 왼쪽에 위치하고 있는 빌딩들 전부보다 오른쪽 빌딩이 낮은 것이므로 스택에 담겨있는 빌딩 수만큼 cnt를 올려준다.
            // (주의) 오른쪽 빌딩을 sLeft에 담아주기 전에 카운트 먼저 해줘야함.
            if(sLeft.peek() > sRight.peek()) {
                cnt += sLeft.size();
                sLeft.push(sRight.pop());
            } else {
                sLeft.pop();
            }
        }

        return cnt;
    }
}

Feedback

항상 시간복잡도를 생각해야한다. 최악의 상황에서 빌딩의 수는 80,000개이고, 첫번째 빌딩의 높이가 10억이고 두번째 빌딩부터 999,999,999로 한층씩 낮아진다고 가정하면, 첫번째 빌딩에서는 79,999개의 빌딩을 벤치마킹할 수 있고, 두번째 빌딩은 79,998개, 세번째 빌딩은 79,997개가 되어 등차수열의 합에 의해 총 벤치마킹할 수 있는 빌딩의 수는
$Sn = {80000 * (79998 + 0) \over 2} = 3,199,920,000$
이므로 int의 범위를 벗어나기 때문에 결과는 long 타입 변수에 저장해주어야 한다.

첫번째 제출 시 런타임 에러가 발생하였다. 그 이유는 가장 오른쪽 빌딩이 가장 높은 빌딩일 경우, 반복분을 돌면서 결국에는 sLeft에는 원소가 하나도 남아있지 않고, sRight에 원소 하나만 남게될 것이다. 이 경우 일단 반복문을 들어와서 sRight에 있는 원소를 sLeft로 옮기게 되는데, 그 이후에 sRight.peek으로 접근을 하려고해서 발생하는 문제였다. 따라서 sRight가 비어있는지에 대한 체크를 별도로 해주었다.