📌 문제
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.
히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.
⚔ 입력 및 출력
입력
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 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
👀 문제 해석
주어진 문제는 히스토그램에서 가장 넓은 직사각형의 넓이를 구하는 문제이다. 히스토그램은 서로 다른 높이의 직사각형들로 이루어진 막대 그래프 형태이며, 각 직사각형의 너비는 동일하게 1이다. 문제의 핵심은 히스토그램의 임의의 연속된 직사각형들 중에서 가장 넓은 직사각형의 넓이를 찾는 것이다.
이 문제는 어떻게 분류할 수 있을까? 여러가지 풀이 방법이 있을 것 같은데 기본적으로 자료구조와 탐색 알고리즘에 속한다고 볼 수 있을 것 같다. 나의 경우에는 스택을 활용해서 풀어보려고 한다. 각 직사각형의 높이를 기준으로 연속된 영역을 얼마나 확장할 수 있는지를 계산하는 것이 핵심인데, 직관적으로 보자면 이 과정에서 완전 탐색으로도 구해질 텐데, 요구 사항의 입력 크기 100,000에 대해서 전체를 다 탐색하면 풀기 힘들다. 따라서 모든 구간을 일일이 계산하는 방식보다는 스택을 이용한 탐색으로 접근하려고 한다. 즉, 시간 복잡도를 O(n) 수준으로 최적화해야 하는 방식으로 스택을 사용해보자.
이 문제를 좀 더 전문적인 용어로 분류해보자면 모노토닉 스택이라는 기법이 필요하다. 모노토닉 스택은 특정한 순서를 유지하는 스택으로, 이 문제에서는 직사각형의 높이가 증가하거나 감소하는 패턴을 따라 넓이를 계산할 수 있다.
🔎 접근
먼저 생각해볼 점은 어떻게 각 직사각형이 확장될 수 있는지, 즉 각 직사각형을 기준으로 좌우로 얼마나 넓은 영역을 차지할 수 있을지를 빠르게 계산할 방법이다. 스택을 사용해 각 직사각형의 높이를 저장하고, 히스토그램을 순차적으로 스캔하면서 스택에서 값을 뽑아내며 넓이를 계산할 수 있다.
먼저 직사각형의 계산 메커니즘에 대해 생각해보자. 각 직사각형은 자신보다 낮거나 같은 높이의 직사각형이 나올 때까지 좌우로 확장할 수 있다.
그렇다면, 한 직사각형이 확장할 수 있는 가장 큰 넓이를 계산하려면, 이 직사각형보다 낮은 높이가 나올 때마다 직사각형의 높이를 기준으로 넓이를 계산해야 한다. 이 때 스택을 사용하는 이유는 직사각형들의 높이를 순차적으로 저장하고, 낮은 직사각형이 나오면 이전 직사각형의 확장을 종료시키기 위함이다.
즉, 스택에 들어가는 직사각형들은 항상 높이가 오름차순이 되도록 유지한다. 스택에 들어간 직사각형은 더 높은 직사각형이 나올 때까지 계속 확장할 수 있기 때문에, 그 상태를 유지하기 위해 우리는 스택을 이용해 높이를 관리한다. 그리고 현재 직사각형이 스택의 꼭대기 값보다 낮아질 때마다 스택에서 값을 꺼내면서 해당 직사각형의 넓이를 계산할 수 있게 된다.
해당 내용은 코드를 구현하면서 구체적인 예시와 함께 살펴보도록 하자.
구체적인 알고리즘 스텝으로는, 히스토그램의 첫 번째 직사각형부터 차례대로 살피는 것이 첫 번째 스텝일 것이다.
- 각 직사각형을 차례대로 살피면서 스택에 저장한다. 만약 현재 직사각형이 스택의 꼭대기 값보다 크거나 같다면, 직사각형을 스택에 쌓는다. 이는 이 직사각형이 앞으로 더 확장될 가능성이 있음을 나타낸다.
- 현재 직사각형이 스택의 꼭대기 값보다 낮다면, 스택에서 값을 꺼내며 직사각형의 넓이를 계산한다. 이때 꺼내는 직사각형은 현재 직사각형보다 높기 때문에, 해당 높이가 차지하는 최대 영역을 계산할 수 있다. 꺼낸 직사각형의 넓이, 즉 가로 길이는
(현재 인덱스 - 스택에서 다음으로 남아 있는 값의 인덱스 - 1)을 통해 구한다. - 모든 직사각형에 대해 순회가 끝난 뒤에도 스택에 남아 있는 직사각형들이 있을 수 있다. 이때는 스택에 남아 있는 직사각형들에 대해 같은 방식으로 넓이를 계산한다. 스택이 빌 때까지 계속 반복하며 넓이를 구한다. 이 과정에서 마지막 남은 직사각형들은 전체 히스토그램에서 끝까지 확장될 수 있으므로, 마지막 직사각형까지 확장 가능한 넓이를 계산해준다.
이 알고리즘은 한 번의 스캔으로 스택에서 값을 넣고 빼는 작업을 반복하게 되므로, 시간 복잡도는 O(n)이다.
🕹 풀이 코드 구현
이제 코드를 작성해보자. 먼저 백준 사이트 특성에 따라 입력부터 처리해주어야 한다.
1. 입력 처리 및 종료 조건
입력은 여러 개의 테스트 케이스로 이루어져 있고, 마지막 입력은 '0'으로 주어진다.
while (true) {
String[] input = br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
// 종료 조건 (마지막 입력 0)
if (n == 0) {
break;
}
int[] heights = new int[n];
for (int i = 0; i < n; i++) {
heights[i] = Integer.parseInt(input[i + 1]);
}
// 가장 큰 직사각형 넓이 계산
System.out.println(getMaxRectangleArea(heights));
}
여기서 n은 히스토그램에 포함된 직사각형의 수를 나타낸다. 배열 heights에 각 직사각형의 높이를 저장한다. 테스트 케이스가 끝나면 getMaxRectangleArea 함수를 호출하여 결과를 출력한다.
2. 스택을 사용한 최대 직사각형 넓이 계산
본격적으로 알고리즘 구현이 필요한 함수이다.
히스토그램에서 가장 큰 직사각형의 넓이를 계산하는 함수로서 getMaxRectangleArea 메서드를 구현한다.
public static long getMaxRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
long maxArea = 0;
int n = heights.length;
먼저, 스택과 최대 넓이를 저장할 변수를 초기화한다. 스택은 직사각형의 인덱스를 저장하여 각 직사각형이 확장될 수 있는 구간을 추적하는 역할을 한다. maxArea는 현재까지 발견된 가장 큰 넓이를 저장하는 변수이다.
3. 스택을 사용해 히스토그램 탐색
히스토그램을 순차적으로 탐색해보자. 이때, 스택에 높이를 저장하거나, 스택에서 값을 꺼내면서 넓이를 계산하는 로직이 필요하다.
for (int i = 0; i < n; i++) {
// 현재 높이가 스택의 top보다 작으면 스택에서 pop하여 넓이 계산
while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
int height = heights[stack.pop()]; // 스택에서 pop한 높이
int width = stack.isEmpty() ? i : i - stack.peek() - 1; // 직사각형의 너비 계산
maxArea = Math.max(maxArea, (long) height * width); // 최대 넓이 갱신
}
// 현재 인덱스 스택에 추가
stack.push(i);
}
n 개의 주어지는 height에 대해서 순회하면서, 현재 높이가 스택의 top보다 작으면 스택에서 pop하여 넓이 계산하고, 그렇지 않으면, 즉 스택이 비어있거나 (처음인 경우) 스택에 들어있는 이전 height 보다 같거나 높으면 스택에 넣는다. 물론 작은 경우에도 pop 한 이후의 로직을 수행한 후 자기 자신을 넣는다.
여기서 while 문을 좀 더 살펴보자. 스택이 비어있지 않으면서 스택의 top 값보다 작은 높이를 만나면 실행된다. 스택에서 직사각형의 높이를 꺼내고, 해당 직사각형의 넓이를 계산한 후, 최대 넓이를 갱신한다. width는 꺼낸 직사각형이 차지하는 가로 길이이며, 이는 스택에 남아 있는 인덱스와 현재 인덱스 차이로 계산된다.
스택의 가로 길이를 구하는 로직은 stack.isEmpty() ? i : i - stack.peek() - 1 이다. 어째서일까? 이를 이해하기 위해서는 스택이 저장하는 데이터와 그 역할을 이해해야 한다.
현재 스택은 히스토그램 막대들의 인덱스를 저장하며, 높이가 증가하는 순서로 관리되고 있다. 이것이 핵심이다. 이때, 각 막대는 자신보다 낮은 막대가 나타날 때까지 확장될 수 있다. 이때 pop된 막대의 최대 확장 너비는 스택이 비었는지 여부에 따라 달라진다. 다음 두가지 케이스가 가능할 것이다.
1. 스택이 비어 있는 경우
스택이 비어 있다는 것은, 현재 직사각형의 왼쪽에 자신보다 낮은 높이의 직사각형이 전혀 없다는 상황을 의미한다. 즉, 현재 직사각형은 왼쪽 끝까지 확장될 수 있다는 뜻이다. 이 경우는 히스토그램의 초반부에서 큰 막대가 나오고, 이후에 낮은 막대가 등장하는 구조에서 발생한다.
예를 들어, 히스토그램이 6 0 0 0 0과 같은 경우라면, 처음 6이 스택에 push되고, 그다음 높이가 0인 막대가 등장하는 순간 스택에서 6을 pop한다. 이때 스택이 비어 있으면, pop된 직사각형은 왼쪽 끝부터 현재 인덱스까지 확장될 수 있다.
스택이 비어 있는 경우 너비는 i, 즉 현재 인덱스까지 확장 가능한 넓이를 의미한다. 이때 pop된 직사각형은 왼쪽 끝까지 확장될 수 있으므로, 너비는 i로 계산된다.
예를 들어, i = 1에서 스택이 비어 있는 상태에서 pop된 막대가 있다면, 이 직사각형은 i = 0부터 현재 인덱스까지 확장될 수 있다는 뜻이다.
또 다른 예시로 히스토그램이 6, 8, 5인 상황을 생각해보자.
- i = 0: 높이
6이 스택에 push된다. 스택:[6]. - i = 1: 높이
8이 스택에 push된다. 스택:[6, 8]. - i = 2: 높이
5가 이전 막대들보다 작으므로, while 문이 실행되며 스택에서 pop이 발생한다.- 먼저
8이 pop되고, 이때 스택은 비어 있지 않으므로 너비는1로 계산된다.8 * 1 = 8이 되며, 최대 넓이를 갱신한다. - 이후, 다시 while 문이 실행되며
6이 pop된다. 이때는 스택이 비어 있으므로6은 히스토그램의 왼쪽 끝까지 확장될 수 있다. 이때 너비는i = 2가 되고, 넓이는6 * 2 = 12가 된다.
- 먼저
- 마지막으로
5가 스택에 push된다. 스택:[5].
- 만약에 여기서
4가 추가 되면 어떨까? 어디가 계산되어야 할까? 5의 입장에서 최대 넓이는 다음 그림에서 보는 것과 같이 처음 시작 지점부터 5 높이까지일 것이다.
4시점에서 while 문이 작동하면서5가 pop 되고, 이때 스택은 비어 있으므로 index인 3이 i가 되므로, 5 * 3 = 15 라는 계산이 정확하게 나오게 된다.
2. 스택이 비어 있지 않은 경우
스택이 비어 있지 않다는 것은 pop된 직사각형의 왼쪽에, 자신보다 같거나 낮은 직사각형이 존재한다는 의미다. 이 직사각형은 pop된 직사각형이 확장될 수 있는 최대 구간을 제한하는 역할을 한다. 즉, 이 스택의 top에 있는 직사각형은 pop된 직사각형보다 낮은 가장 가까운 직사각형으로, 이 막대의 오른쪽까지는 확장할 수 있지만, 그 막대 이후로는 확장할 수 없다.
이때 너비는 현재 인덱스에서 스택의 top에 있는 인덱스의 차이로 계산되며, -1을 하는 이유는 pop된 직사각형이 확장할 수 있는 최대 범위는 스택의 top에 있는 막대 바로 직전까지이기 때문이다. 이를 통해 pop된 직사각형의 최대 확장 너비를 구할 수 있다.
위에서 사용했던 예시에서 직사각형이 좀 더 추가된 상황을 생각하여 예를 들어보자.
6, 8, 5, 4 에서 이제 5, 6, 4가 추가되는 상황을 생각해보자. i가 3인 시점까지 위에서 계산을 했고, 이제 4만이 스택에 남아 있는 상황이다. 이때, 5, 6은 while문에 타지 않으므로 차례로 스택에 추가되어 다음 그림과 같이 4, 5, 6이 스택에 쌓여 있는 상황이 될 것이다.
이제 i = 6, 즉 두 번째 4가 등장한다. 이 시점에서 현재의 높이 4는 스택에 있는 6, 5보다 작으므로, 다시 while 문이 실행되어 pop이 발생한다.
- 첫 번째 pop: 스택의 top 값인
6이 pop된다. 이때 스택에는 아직5가 남아 있으므로, 너비는i - stack.peek() - 1로 계산된다. 즉,6 - 4 - 1 = 1이므로, 넓이는6 * 1 = 6이다. 그림으로 보면 다음과 같다.
- 두 번째 pop: 다시 while 문이 실행되어 이번에는 스택의 top 값인
5가 pop된다. 이때도 스택에4가 남아 있으므로 너비는i - stack.peek() - 1로 계산된다. 즉,6 - 3 - 1 = 2가 되므로, 넓이는5 * 2 = 10이 된다.
- 이후, 스택에 있는
4와 현재4가 동일한 높이이므로, 현재4도 스택에 push된다. 스택:[4, 4].
따라서 정리해보자면 다음과 같다.
- i = 6에서 while 문이 실행되어 스택의 top 값들이 pop될 때, 스택이 비어 있지 않으면 pop된 직사각형이 확장할 수 있는 범위는 스택의 top에 남아 있는 직사각형의 인덱스까지 제한된다.
- 이로 인해, pop된 직사각형의 너비는 현재 인덱스에서 스택의 top에 남아 있는 인덱스의 차이로 계산된다. 그리고 pop된 직사각형은 그 직사각형보다 작거나 같은 이전 막대까지만 확장될 수 있다.
6, 8, 5, 4, 5, 6, 4에서 두 번째4가 등장할 때, 스택에 있는 값들이 순차적으로 pop되며 각각의 직사각형 넓이가 계산되고, 그 후 현재4가 스택에 push되면서 과정이 반복된다.
4. 스택에 남은 직사각형 처리
이제 마지막으로, 히스토그램을 다 스캔한 후의 상황을 생각해보자. 현재의 예시에서처럼 스택에 값이 남아 있을 수 있다. 이때는 히스토그램의 끝까지 확장할 수 있는 직사각형들이므로 이들을 처리해주어야 한다.
while (!stack.isEmpty()) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? n : n - stack.peek() - 1;
maxArea = Math.max(maxArea, (long) height * width);
}
스택에 남아 있는 직사각형들은 히스토그램의 끝까지 확장될 수 있으므로, 이들에 대해 최대 넓이를 계산한다. 예를 들어, 현재 예시의 4, 4를 생각해보자.
예시: 6, 8, 5, 4, 5, 6, 4
히스토그램을 모두 스캔한 후 스택에는 [4, 4]가 남아 있다.
이제 스택에서 남은 직사각형들을 하나씩 pop하여 계산해야 한다. 이때는 더 이상 비교할 막대가 없으므로, 각 직사각형은 히스토그램의 끝까지 확장될 수 있다.
- 첫 번째 pop: 스택의 top 값
4가 pop된다. 이때 스택이 비어 있지 않으므로, 너비는n - stack.peek() - 1로 계산된다. 여기서n = 7(히스토그램의 길이)이고, 스택의 top은 두 번째4이므로, 너비는7 - 3 - 1 = 3이 되어 넓이는4 * 3 = 12가 된다.
- 두 번째 pop: 스택에서 마지막
4가 pop된다. 이제 스택이 비어 있으므로, 이 직사각형은 히스토그램의 왼쪽 끝부터 끝까지 확장될 수 있다. 너비는n = 7이 되고, 넓이는4 * 7 = 28이 된다. 따라서 이 직사각형이 히스토그램에서 차지하는 최대 넓이는28이다.
예시의 4, 4가 남아 있을 때, 첫 번째 4는 오른쪽 끝까지 확장될 수 없으므로 제한된 범위에서 넓이를 계산하지만, 마지막 4는 전체 히스토그램을 커버할 수 있어 최대 넓이를 계산할 수 있다.
돌이켜 보면 이로써 모든 범위의 직사각형을 효율적으로 계산할 수 있었다.
5. 최종 결과 반환
최종적으로 구해진 최대 넓이를 반환한다.
return maxArea;
📌 최종 제출 코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
String[] input = br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
if (n == 0) {
break;
}
int[] heights = new int[n];
for (int i = 0; i < n; i++) {
heights[i] = Integer.parseInt(input[i + 1]);
}
System.out.println(getMaxRectangleArea(heights));
}
}
public static long getMaxRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
long maxArea = 0;
int n = heights.length;
// 히스토그램 높이를 순회하면서
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, (long)height * width);
}
stack.push(i);
}
// 남아 있는 직사각형 처리
while (!stack.isEmpty()) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? n : n - stack.peek() - 1;
maxArea = Math.max(maxArea, (long)height * width);
}
return maxArea;
}
}
추가로 테스트 케이스로 다음과 같은 입력을 사용해보자.
@Test
public void testValidCases() throws IOException {
// 테스트 케이스 1: 예제 입력 1 (7개의 높이가 주어진 경우)
Assertions.assertEquals(8, getMaxRectangleArea(new int[]{2, 1, 4, 5, 1, 3, 3}));
// 테스트 케이스 2: 모든 직사각형의 높이가 동일한 경우
Assertions.assertEquals(4000, getMaxRectangleArea(new int[]{1000, 1000, 1000, 1000}));
// 테스트 케이스 3: 직사각형의 높이가 모두 1인 경우
Assertions.assertEquals(7, getMaxRectangleArea(new int[]{1, 1, 1, 1, 1, 1, 1}));
// 테스트 케이스 4: 단일 직사각형
Assertions.assertEquals(5, getMaxRectangleArea(new int[]{5}));
// 테스트 케이스 5: 높이가 0인 직사각형 포함된 경우
Assertions.assertEquals(9, getMaxRectangleArea(new int[]{0, 3, 3, 3, 0}));
// 테스트 케이스 6: 높이가 다양한 경우
Assertions.assertEquals(12, getMaxRectangleArea(new int[]{6, 2, 5, 4, 5, 1, 6}));
// 테스트 케이스 7: 증가하다가 감소하는 패턴
Assertions.assertEquals(12, getMaxRectangleArea(new int[]{1, 2, 3, 4, 5, 3, 2}));
// 테스트 케이스 8: 모두 0인 경우
Assertions.assertEquals(0, getMaxRectangleArea(new int[]{0, 0, 0, 0, 0}));
// 테스트 케이스 9: 큰 값이 포함된 경우
Assertions.assertEquals(12, getMaxRectangleArea(new int[]{4, 4, 4, 1, 1, 1, 12}));
}
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 앵무새 (자바 풀이 - 큐, 배열, 해시맵을 곁들인) (1) | 2024.10.12 |
|---|---|
| [백준] 좋은 친구 (자바 풀이) (0) | 2024.10.11 |
| 백준 5397 키 로거 (JAVA 자바 풀이) (0) | 2024.01.03 |
| 백준 2118 두 개의 탑 (JAVA 자바 풀이) (1) | 2024.01.02 |
| 백준 11725 트리의 부모 찾기 (JAVA 자바 풀이) (0) | 2023.12.31 |
