[BOJ] 6198: 옥상 정원 꾸미기 (JAVA)

문제

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

 

여담

탑 문제와 거의 유사해서 그 문제를 풀 때 배웠던 아이디어를 사용해서 풀었다. 조금 다른 부분이 있었지만 잘 생각해 보면 풀 수 있는 문제라 한 번에 풀 수 있었던 것 같다. 역시 많이 풀어보는 것이 중요한 듯!

 

풀이

이 문제도 N이 최대 80,000개라 이중 반복문을 사용하면 시간 초과가 발생한다. 따라서 스택을 사용해서 시간 초과가 발생하지 않도록 풀이하면 된다. 

 

따라서 아래의 과정을 각 빌딩마다 반복해서 수행하면 된다. 

1. 스택이 비어있는 경우
   • 현재 빌딩을 스택에 push하기
2. 스택이 비어있지 않는 경우
   • 스택에 peek한 빌딩의 높이 < 현재 빌딩의 높이
     • peek한 빌딩을 pop하고, 확인한 빌딩의 수 더하기
   • 스택에 peek한 빌딩의 높이 > 현재 빌딩의 높이
     • 현재 빌딩을 스택에 push하고 현재 빌딩의 탐색을 종료하기

 

이때, "peek한 빌딩의 높이 < 현재 빌딩의 높이"인 경우 peek한 빌딩을 pop하기 때문에, 1번 빌딩을 탐색할 때는 스택에 2번, 3번 빌딩만 존재한다. 그래서 각 빌딩에서 볼 수 있는 빌딩의 수를 따로 기록하도록 했다. 자세한 내용은 아래의 예시와 코드를 참고하면 된다.

 

예시

빌딩의 높이가 10 3 7 4 12 2일 때 풀이 과정은 다음과 같다. 참고로 탑 문제와 달리 → 방향으로 건물을 바라보기 때문에, 탐색은 ← 방향으로 수행해야 한다. (1번 빌딩을 탐색할 때 2번 빌딩이 스택에 있어야 하므로)

 

6번 빌딩

처음에는 스택이 비어있으므로 6번 빌딩을 스택에 push한다.

 

5번 빌딩

스택에서 peek한 빌딩의 높이는 2이고, 현재 빌딩의 높이는 12이다. 즉, 현재 빌딩이 더 높기 때문에 peek한 빌딩(=6번)을 pop하고 현재 빌딩에서 볼 수 있는 빌딩의 수를 기록한다. 이때, pop한 빌딩에서 볼 수 있는 빌딩이 있을 수 있기 때문에, total[5] += total[6] + 1 와 같이 이전 값을 함께 고려해서 값을 기록한다.

 

6번 빌딩을 pop하면 스택이 비어있기 때문에 5번 빌딩을 스택에 push한다.

 

4번 빌딩

스택에서 peek한 빌딩의 높이는 12이고, 현재 빌딩의 높이는 4이다. 즉, peek한 빌딩이 더 높기 때문에 현재 빌딩을 스택에 push한다.

 

3번 빌딩

스택에서 peek한 빌딩의 높이는 4이고, 현재 빌딩의 높이는 7이다. 즉, 현재 빌딩이 더 높기 때문에 peek한 빌딩(=4번)을 pop하고 현재 빌딩에서 볼 수 있는 빌딩의 수를 기록한다.(total[3] += total[4] + 1)

 

아직 스택이 비어있지 않으므로 다시 비교를 시작한다. 스택에서 peek한 빌딩의 높이는 12, 현재 빌딩의 높이는 7이다. 즉, peek한 빌딩의 높이가 더 높으므로 현재 빌딩을 스택에 push한다.

 

2번 빌딩

스택에서 peek한 빌딩의 높이는 7, 현재 빌딩의 높이는 3이다. 즉, peek한 빌딩의 높이가 더 높으므로 현재 빌딩을 스택에 push한다.

 

1번 빌딩

스택에서 peek한 빌딩의 높이는 3이고, 현재 빌딩의 높이는 10이다. 즉, 현재 빌딩이 더 높기 때문에 peek한 빌딩(=2번)을 pop하고 현재 빌딩에서 볼 수 있는 빌딩의 수를 기록한다. (total[1] += total[2] + 1)

 

아직 스택이 비어있지 않으므로 다시 비교를 시작한다. 스택에서 peek한 빌딩의 높이는 7, 현재 빌딩의 높이는 10이다. 즉, 현재 빌딩이 더 높기 때문에 peek한 빌딩(=3번)을 pop하고 현재 빌딩에서 볼 수 있는 빌딩의 수를 기록한다. (total[1] += total[3] + 1)

 

스택에서 peek한 빌딩의 높이는 12, 현재 빌딩의 높이는 10이다. 즉, peek한 빌딩의 높이가 더 높으므로 현재 빌딩을 스택에 push한다.

 

모든 빌딩을 검사하면 비교하는 과정을 종료한다.

 

코드

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

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());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Stack<Building> stack = new Stack<>();
        int[] total = new int[N];
        for (int i = N - 1; i >= 0; i--) {
            if (stack.isEmpty()) {
                stack.push(new Building(arr[i], i));
            } else {
                while (true) {
                    if (stack.isEmpty()) {
                        stack.push(new Building(arr[i], i));
                        break;
                    }

                    if (stack.peek().height < arr[i]) {
                        Building pop = stack.pop();
                        total[i] += total[pop.idx] + 1;
                    } else {
                        stack.push(new Building(arr[i], i));
                        break;
                    }
                }
            }
        }

        long sum = 0;
        for (int i = 0; i < N; i++) {
            sum += total[i];
        }
        System.out.println(sum);
    }

    static class Building {
        int height;
        int idx;

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

---