0x05 백준 6198 (옥상 정원 꾸미기)

📚 오늘의 문제

링크 : 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번째 줄까지 각 빌딩의 높이가 h 입력된다. (1 ≤ h ≤ 1,000,000,000)

출력

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

예제 입력 1

6
10
3
7
4
12
2

예제 출력 1

5

🔑 키워드.

특정 값보다 큰 값 OR 작은 값이 나올 때까지 확인해야 할 때?

→stack?

문제 풀이

그림을 그려보면서 어떤 기준으로 문제를 풀어야 할지 감을 잡았다. 솔직히 문제 분류에 스택이라는 말이 없었다면 문제를 쉽게 못 풀었을 것 같다.

관리인이 보는 방향이 → (오른쪽) 방향 이므로 배열의 끝에서부터 시작해 스택을 쌓아 나가면서 풀이를 진행했다. N+1 만큼의 int 배열을 선언하고 마지막 원소에 1,000,000,000을 넣어줌으로써 관리인이 건물의 끝을 바라볼 때 더 이상의 건물을 바라보지 않도록 했다.

건물의 높이를 저장하는 stack과 해당 건물의 index를 저장하는 stack, 두 스택을 사용하여 문제를 풀었다. Pair과 같은 자료구조를 사용하는 방법도 있었지만 조금 더 직관적으로 문제를 풀고 싶었기 때문에 스택 두개를 사용했다. 다음에는 다른 자료구조를 사용하여 문제를 풀어보도록 해야겠다.

stack이 empty이거나, stack의 top이 현재 빌딩의 높이보다 크거나 같을 때까지 pop을 진행한다. 그리고 (높이가 같거나 높은 index - 현재 Index -1)을 count에 더해준다.

처음에 count를 int형으로 선언해주었는데, 빌딩의 개수가 80,000이고 만약 내림차순으로 정렬되어 있다면, 80000 + 79999 + 79998 . . . + 2 + 1 이므로 최악의 경우 count가 320,004,000이 되어버린다.

count를 Long타입으로 재선언 후 문제를 해결할 수 있었다.

package week4;

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

public class boj6198 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int [] arr = new int[N+1];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        arr[N] = 1000000000;
        long count =0;
        Stack<Integer> stack = new Stack<>(); //빌딩의 층 수를 저장하는 stack
        Stack<Integer> stack2 = new Stack<>(); //인덱스를 저장하는 stack
        for(int i = N; i>=0; i--){
            while(!stack.isEmpty()&&stack.peek()<arr[i]) {
                stack.pop();
                stack2.pop();
            }
            if(!stack.isEmpty()){
                count+=stack2.peek()-i-1; // 높이가 같거나 높은 index - 현재 Index -1을 count에 더해준다.
            }
            stack.push(arr[i]);
            stack2.push(i);
        }
        System.out.println(count);
    }
}

🎯 결론

❗ 그림을 그려보면서 어떤 자료구조, 알고리즘을 사용할 지 결정하는 것이 중요하다. 또한 자료형의 범위를 잘 고려해보자.