[백준] 1725 히스토그램 - Java

 

 

 

문제 출저

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

1725번: 히스토그램

 

 

 

문제 풀이

히스토그램이 주어진다. 이 때, 히스토그램 내부에 가장 넓이가 큰 직사각형의 넓이를 구해야 한다.

 

 

Stack을 이용해 문제를 풀었습니다.

Stack에는 현재 탐색하는 막대보다 작거나 같은 값만이 들어갈 수 있습니다. 

히스토그램의 막대의 위치를 Stack에 넣으며 탐색합니다. 

Stack에 담긴 이전 막대의 높이가 현재 탐색하는 막대의 높이보다 크다면 스택에서 꺼내(pop) 넓이를 계산합니다.

넓이는 막대의 높이(막대의 높이) * 가로(막대의 위치 - Stack의 가장 위의 위치) 입니다.

 

이런 식으로 정답을 계속 업데이트해서 가장 큰 직사각형의 넓이를 구할 수 있습니다.

문제의 stack 로직 계산 n+2의 배열로 하여 처음(인덱스 : 0)과 끝(인덱스 : n-1)을 높이 0으로 설정합니다. 

처음과 끝을 0으로 설정함으로 초기값 설정이 수월하고 끝에서 이 때까지 담긴 스택 계산이 무조건적으 이루어지기 때문입니다.

 

 

소스 코드

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

/*
히스토그램
https://www.acmicpc.net/problem/1725

int의 범위는 20억

2% 틀림
가로에 설정을 고치니 해결

11% 틀림

 */

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[] squares = new int[n+2];
        for(int i = 1; i < n+1; i++) {
            squares[i] = Integer.parseInt(br.readLine());
        }

        Stack<Integer> stack = new Stack<>();
        stack.add(0);
        int answer = 0;

        for(int i = 1; i < n+2; i++) {
            while(!stack.isEmpty() && squares[stack.peek()] > squares[i]) {
                int index = stack.pop();
                int height = squares[index];
                int garo = i - stack.peek() - 1;

                // System.out.println(i + " " + index + " " + height + " " + (i - index));

                answer = Math.max(answer, height * garo);
            }
            stack.add(i);
        }

        System.out.println(answer);

    }

}