[BOJ][P5] 6549 히스토그램에서 가장 큰 직사각형

문제 내용

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0 6이 하나가 주어진다

히스토그램 내에서 만들 수 있는 가장 큰 직사각형의 넓이를 구하는 문제다.

문제 접근 (의식의 흐름대로)

딱 문제를 보고 들었던 생각들을 정리하면 다음과 같다.

• 일단 n이 10만이고, 직사각형 높이가 10억이니까 이걸 전부 반복시키면 안되겠다
  시간 복잡도를 무조건 생각해야겠다.
• 높이가 10억이나 되니, 넓이를 계산하다 보면 int 범위를 넘을 수 있겠고. 결과값 담을 자료형은 long으로 쓰는 건 일단 확정
• 근데 변형되는 넓이를 어떻게 구해야 할지, 최대 넓이가 되는 형태를 어떻게 찾아야 할지 전혀 감이 안 왔다. DP를 써야 하나?
• 결국 풀지 못하고 힌트를 봤고. '세그먼트 트리'라는 키워드가 있어서 이 부분을 공부하고 다시 풀어보기를 했으나 결국 못풀었다.

회고 & 풀이 방법

→ 스택 자료구조를 위한 풀이방법

→ 분할 정복 풀이 방법

→ 세그먼트 트리를 이용한 풀이방법

총 3가지가 있다는것을 알았다.

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        while (true) {
                st = new StringTokenizer(br.readLine());

                int n = Integer.parseInt(st.nextToken());

                if (n == 0) break;

                int[] h = new int[n + 1];

                for (int i = 0; i < n; i++) {
                    h[i] = Integer.parseInt(st.nextToken());  // 각 막대의 높이가 들어감
                }

                Deque<Integer> stack = new ArrayDeque<>(n + 1);

                long max = 0;  // 최대값

                for (int i = 0; i <= n; i++) {
                    int cur = h[i]; // cur 은  0 ~ n 까지에서 해당 번호의 막대 높이

                    while (!stack.isEmpty() && h[stack.peek()] > cur) { // 스택이 비어있때는 -> h[stack.peek()] > cur 를 실행하지 않음
                        int top = stack.pop();

                        int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                        long area = (long) h[top] * (i - left);

                        if (area > max) max = area;
                    }

                    stack.push(i);
                }

                sb.append(max).append('\n');
            }

            System.out.print(sb);
    }

}

일단 내가 푼 풀이는 아니지만 굉장히 깔끔한게 stack 으로 푼 방법이다.

핵심 코드인 아래만 봐도 무방하다

  for (int i = 0; i <= n; i++) {
        int cur = h[i]; // cur 은  0 ~ n 까지에서 해당 번호의 막대 높이

        while (!stack.isEmpty() && h[stack.peek()] > cur) { // 스택이 비어있때는 -> h[stack.peek()] > cur 를 실행하지 않음
            int top = stack.pop();

            int left = stack.isEmpty() ? 0 : stack.peek() + 1;
            long area = (long) h[top] * (i - left);

            if (area > max) max = area;
        }

        stack.push(i);
    }

h[i] 와 i 를 이해하고 while (!stack.isEmpty() && h[stack.peek()] > cur) {} 이 부분만 이해하면 될거 같다.

해당 문제는 BOJ 17298 문제랑도 비슷한데 해당 코드를 해석하면

!stack.isEmpty() 은 stack의 비어있는지 없는지를 확인하고 이를 확인하면

h[stack.peek()] > cur 를 통해 현재 stack 의 index 값을 peek()을 통해 확인 하여 스택 값을 호출하는 형식이다 . 처음에 이해가 안됬던 부분은? !stack.isEmpty() && h[stack.peek() 이 부분에서 stack에 값이 없는데 peek 이 어떻게 가능한지라는 의문이 있었다. → 해당부분은 && 의 연산으로 앞부분의 참/거짓 여부를 먼저 파악하기 때문에 앞에 false 인 순간 뒤에 stack의 peek은 동작하지 않는다고 한다.

이번 문제와 오큰수를 풀어본 후기로는 while (!stack.isEmpty() && h[stack.peek()] > cur) {} 이 부분을 통해 stack의 흐름제어를 이용하는것도 하나의 알고리즘 방법이라는것을 알았다.

구현도 쉽지만 아이디어적으로 생각이 나기 힘든 부분이었다고 생각한다.

일주일뒤에 다시 풀어봐야겠다.