[Java] 히스토그램

1. 문제 설명

아래에서 보는 그림처럼 서로 폭이 모두 같은 직사각형들이 서로 밀착하여 바닥에 붙어있는 모양을 상상해보자. 이 도형의 내부를 2차원적으로 생각해 보았을 때, 이 히스토그램의 바닥면과 옆면의 방향에 평행한 변을 가지는 직사각형이 존재할 수 있다.

이러한 직사각형 들이 히스토그램 내부에서 가질 수 있는 가장 큰 넓이를 구해보자

입력 형식

첫 줄에는 테스트케이스의 수를 나타내는 자연수 T가 주어진다. 이후 총 T개의 테스트케이스에 대한 입력이 순서대로 주어지며 각 테스트케이스는 총 두 줄의 입력으로 이루어져 있다.

• 테스트케이스의 첫 줄에는 히스토그램을 구성하는 직사각형 모양 기둥의 수를 나타내는 10만 이하의 자연수 N이 주어진다.
• 테스트케이스의 두 번째 줄에는 각 직사각형 모양 기둥의 높이가 공백으로 구분되어 왼쪽부터 순서대로 주어진다.
  각 직사각형의 높이는 10만 이하의 자연수이다.

출력 형식

각 테스트케이스 별로 한 줄에 히스토그램 내부에 존재할 수 있는 직사각형의 최대 넓이를 계산하여 출력한다.

2. 알고리즘 접근

하나하나 탐색하는 것은 시간초과가 걸리니 자료구조 스택을 사용해서 최적화하자
스택을 어떻게 사용해야할까?

• 기둥 1 ~ n까지를 순회한다
• 기둥을 순회하며 하나를 선정한다
• 만약 선정한 기둥이 전 기둥보다 작다면 이전 기둥을 스택에서 제거한다(pop)
• 이 때 삭제할 기둥에서 뻗어나갈 수 있는 가장왼쪽 기둥과 오른쪽 기둥을 찾아 넓이를 구해 최댓값을 갱신한다
• 스택에 해당 기둥을 추가한다(push)

위와 같은 방법을 사용한다면 순회 데이터의 마지막값이 스택에서 제거하지 않을 경우
해당 기둥의 넓이를 구하는 수행을 하지 않으니 가짜데이터 매우 작은 값을 넣어
마지막 기둥까지 넓이를 구하는 처리를 해준다.

3. 소스코드

package algorithm.comon.chapter5;

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

public class Q5C {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static long getLargestRectangleArea(int n, Histogram[] histograms) {

        Stack<Histogram> continuedHistograms = new Stack<>();
        long answer = 0;

        continuedHistograms.push(new Histogram(-1, 0));
        for(int i = 0; i < n + 1; i++){
            Histogram h = null;
            if(i < n){ // h를 이용해서 순회한다
                h = histograms[i];
            }else{ // i == n 마지막 값에는 가짜 데이터를 넣는다
                h = new Histogram(n, 0);
            }
            // 2 1 4 5 1 3 3
            while (continuedHistograms.size() > 1 && continuedHistograms.peek().height >= h.height){
                Histogram lh = continuedHistograms.pop(); // lh는 스택에서 pop()한 값이 들어간다
                Histogram bh = continuedHistograms.peek();

                long width = h.leftX - bh.rightX; // 너비 공식
                long height = lh.height; // 높이
                long area = width * height; // 넓이 구하기

                answer = Math.max(area, answer); // 기존의 값중에 최대값을 비교
            }
            continuedHistograms.push(h);
        }
        return answer;
    }

    private static void testCase(int caseIndex) throws IOException{
        int n = Integer.parseInt(br.readLine()); // 기둥의 수 n
        Histogram[] histograms = new Histogram[n]; // 객체배열

        // 기둥의 높이 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
           histograms[i] = new Histogram(i, Integer.parseInt(st.nextToken()));
        }

        long answer = getLargestRectangleArea(n, histograms);
        System.out.println(answer);

    }

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

        int caseSize = Integer.parseInt(br.readLine());

        for(int caseIndex = 1; caseIndex <= caseSize; caseIndex++){
            testCase(caseIndex);
        }

    }
}
class Histogram{
    public int leftX; // 인덱스 혹은 히스토그램 왼쪽 변의 x 좌표
    public int rightX; // 히스토그램 오른쪽 변의 x좌표
    public int height;
    Histogram(int index, int height){
        this.height = height;
        this.leftX = index;
        this.rightX = this.leftX + 1;
    }
}