[백준] 6549: 히스토그램에서 가장 큰 직사각형 (Stack) - JAVA

문제집 랜덤풀이

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

 

 

# 문제

 

# 예제

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

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

 

출력: 각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

8
4000

 

# 필요개념

 

처음에 문제를 봤을 때, 높이를 누적으로 어떻게 풀어가야할까? 에 대한 고민이 많이 들었다. 그래서 DP로도 풀어보고, 쌩 구현으로도 해보려했는데 잘 풀리지 않았다. 문제 카테고리를 확인해보니, 스택과 분할정복이 있어서 한번 찾아보았다.

 

풀이 방식을 보니, 사실 분할정복 풀이는 와닿지 않았다. 이걸 분할정복으로 어떻게 하겠다는거지? 라는 의문이 들었고, 일단은 스택으로의 방식을 확인해보았는데 정말 머리를 맞은 기분이었다. 이렇게도 풀 수 있구나 싶어 스택을 이용해 문제풀이를 해보았다.

 

 

기본적으로 스택을 사용하면 peek() 만으로 직전 단계의 높이를 알아낼 수 있다. 해당 문제의 특성상, 높이가 더 낮은 단계에 맞추어 직사각형을 만들 수 있기 때문에, 이전단계가 높이가 더 작거나 같은 경우에는 그냥 스택에 계속 저장하고, 이전단계가 더 커졌을 때, 스택에 들어있는 것들을 pop 하면서 너비를 갱신해나가는 방식을 이용해 문제를 풀 수 있다.

 

너비는 어차피 1이므로, 인덱스를 이용하면 너비를 구하는 건 매우 간단하다.

 

주황색 라인에서 스택을 한 번 털어 직사각형 넓이를 구하고, 노란색 라인에서 한번 더 털 수 있다. 이후에는 높이가 떨어지는 구간이 없으므로, 반복문이 끝난 이후에도 스택을 털어주는 작업이 필요하다.

 

 

이 문제를 통해서 스택을 고려하는 사고 범위가 유연해진 거 같다!

 

# Code

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

// 6549
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            if (n == 0) {
                break;
            }

            long[] heights = new long[n];
            for (int i = 0 ; i < n ; i++) {
                heights[i] = Long.parseLong(st.nextToken());
            }

            long ans = findMaxWeight(heights);
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }

    private static long findMaxWeight(long[] heights) {
        long maxWeight = 0;
        Stack<Integer> histogram = new Stack<>();

        for (int i = 0 ; i < heights.length ; i++) {
            while (!histogram.isEmpty() && heights[histogram.peek()] > heights[i]) {
                int height = (int) heights[histogram.pop()];
                int width = histogram.isEmpty() ? i : i - histogram.peek() - 1;
                maxWeight = Math.max(maxWeight, (long) height * width);
            }
            histogram.push(i);
        }
        while (!histogram.isEmpty()) {
            int height = (int) heights[histogram.pop()];
            int width = histogram.isEmpty() ? heights.length : heights.length - histogram.peek() - 1;
            maxWeight = Math.max(maxWeight, (long) height * width);
        }

        return maxWeight;
    }
}

 

# 결과