문제 요약
히스토그램의 내부에서 그릴 수 있는 가장 큰 사각형의 넓이를 구하여라.
코드
import java.io.*;
import java.util.*;
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().split(" ")[0]);
int ans = 0;
Rect[] data = new Rect[N];
Stack<Rect> stack = new Stack<>();
for (int i = 0 ; i < N ; i++){
data[i] = new Rect(i, Integer.parseInt(br.readLine()));
}
for (int i = 0; i < N ; i++){
if (stack.isEmpty()){
stack.push(data[i]);
}
else{
while (stack.peek().height >= data[i].height) {
Rect temp = stack.pop();
int height = temp.height;
int position = temp.position;
int size;
if (stack.isEmpty()){
size = i * height;
if (size > ans)
ans = size;
break;
}
else {
size = (i - (stack.peek().position + 1)) * height;
}
if (size > ans)
ans = size;
}
stack.push(data[i]);
}
}
while (!stack.isEmpty()){
Rect temp = stack.pop();
int height = temp.height;
int width;
if (stack.isEmpty())
width = N;
else{
width = N - (stack.peek().position + 1);
}
int size = width * height;
if (size > ans)
ans = size;
}
System.out.println(ans);
}
}
class Rect{
public int position;
public int height;
Rect(int position, int height){
this.position = position;
this.height = height;
}
}문제 해결 방법
히스토그램 문제는 크게 2가지 방법으로 해결할 수 있다.
위 코드는 스택을 이용하여 시간복잡도 O(N)으로 문제를 해결한 방법이고, 두 번째 방법은 2104번 부분수열 문제를 해결하는 것과 동일한 방식으로 분할정복을 이용하여 시간복잡도 O(NlogN)으로 문제를 풀 수 있다.
이 페이지에서는 스택을 이용한 문제 풀이에 관해 작성하려 한다.
코드 내용의 설명은 아래와 같다.
Rect class를 만들어 히스토그램을 구성하는 사각형들의 위치와 높이를 담을 수 있는 인스턴스를 생성하여 스택에 저장한다.
이때 스택이 비어있다면 사각형을 바로 스택에 넣고, 스택이 비어있지 않다면 스택의 top에 위치한 사각형의 높이와 새롭게 스택에 들어갈 사각형의 높이를 비교한다. 이때 새롭게 들어갈 사각형의 높이가 더 작거나 같다면 현재 사각형보다 더 작은 사각형이 스택의 상단에 위치하거나 스택이 빌 때까지 스택을 pop하고, pop되는 사각형의 높이를 가지는 가장 큰 사각형의 넓이를 구한 후 이 넓이와 현재까지 구한 최댓값을 비교하여 더 큰 값을 ans라고 하는 변수에 저장한다.
마지막으로 히스토그램의 우측 끝까지 모두 데이터를 받은 후에 스택에 남아있는 사각형들을 pop하면서 각 사각형의 높이로 가질 수 있는 최대 넓이를 계산하여 ans값과 비교하여 더 큰 값을 ans에 저장한 후 리턴한다.
추가 설명
스택에 새로운 원소를 넣을 때 새로운 원소보다 높이가 높거나 같은 원소들은 모두 pop되면서 넓이가 계산된다. 따라서 스택에는 들어있는 사각형들의 높이는 항상 오름차순으로 정렬되어있고, 스택의 top에 위치한 사각형과 top의 바로 밑 사각형 사이에 스택의 top보다 높이가 작은 사각형은 존재할 수 없음을 알 수 있다.
따라서 스택의 상단에 위치하는 사각형을 pop할 때, 해당 사각형의 높이로 가질 수 있는 최대 너비는 pop하는 사각형과 pop 이후 스택의 상단에 위치하는 사각형의 position을 빼면 구할 수 있다. 만약 pop 이후 스택이 비어있다면 해당 사각형의 position 자체가 너비가 될 수 있음을 의미한다. (0~position까지 현재 pop되는 사각형보다 높이가 낮은 사각형은 존재하지 않음을 의미하기 때문이다)
이 방식으로 계산하면 스택에 들어오는 모든 사각형이 각 사각형의 높이로 가질 수 있는 최대 넓이를 한 번에 계산하고 비교하여 ans를 구할 수 있으므로 O(N)의 시간복잡도로 문제를 해결할 수 있다.
