BOJ 6549
위 문제는 백준 사이트의 알고리즘 6549 문제에 관한 설명입니다.
문제
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다.
각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다.
예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.
히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.
입력
입력은 테스트 케이스 여러 개로 이루어져 있다.
각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다.
(1 ≤ n ≤ 100,000)
그 다음 n개의 정수 h1, …, hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다.
이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다.
모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while (true) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int index;
int width;
if (N == 0) break;
int[] height = new int[N];
Stack<Integer> stack = new Stack<>();
long MAX = 0;
for (int i = 0; i < N; i++) {
height[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < N; i++) {
while (!stack.isEmpty() && height[stack.peek()] > height[i]) {
index = stack.pop();
width = stack.isEmpty() ? i : i - stack.peek() - 1;
MAX = Math.max(MAX, (long) width * height[index]);
}
stack.push(i);
}
while (!stack.isEmpty()) {
index = stack.pop();
width = stack.isEmpty() ? N : N - stack.peek() - 1;
MAX = Math.max(MAX, (long) width * height[index]);
}
System.out.println(MAX);
}
}
}
이번 문제는 Stack을 이용해서 푸는 문제였습니다.
0~n까지 순회하며 넓이를 체크합니다.
i 기준 왼쪽으로 만들 수 있는 넓이를 계산합니다.
일단 넓이 계산이 끝나면, 다음 사용을 위해 i를 push합니다.
넓이 계산은 스택의 top을 비교하면서 진행합니다.
h[top]>h[i]여야 top을 포함하여 넓이를 계산할 수 있습니다.
높이는 i가 기준이므로 width*height[i]이 넓이가 됩니다.
최대 넓이를 구해야하므로 Math.max()를 이용하여 max에 최댓값을 넣습니다.
n까지 순회가 끝난 후, 스택을 확인하여 아직 값이 남아있다면
스택 top~n(마지막)까지의 넓이를 계산합니다.