[Java] BaekJoon 1725. 히스토그램, BaekJoon 6549. 히스토그램에서 가장 큰 직사각형(모노톤스택)
히스토그램
문제출처: https://www.acmicpc.net/problem/1725
1725번: 히스토그램
첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은
www.acmicpc.net
문제이해
목표
주어진 히스토그램에 대해, 위그림처럼 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.
풀이
정답 도출 매커니즘 이해
현재 인덱스(now) 기준으로
- 왼쪽에서 자신과 제일 가까우면서 작은 높이의 인덱스 번호 (left[now])
- 오른쪽에서 자신과 제일 가까우면서 작은 높이의 인덱스 번호 (right[now])
- right[now] - left[now] - 1 이 너비가 된다.
- height[now] * (right[now] - left[now] - 1) 가 인덱스 now일때 구할 수 있는 직사각형의 넓이이다.
정답: Max(각 인덱스에서 구한 넓이들)
그렇다면 어떻게 left와 right에 제일 가까우면서 작은 높이 번호를 저장할 수 있을까 ??
해답은 모노톤 스택(Monoton-Stack) 이다.
모노톤 스택
- 오름, 내림 차순을 유지한 스택을 의미한다.
이 스택을 사용하면 이전에 있던 값들 중 (Stack안에 있는 값들)
자기 자신보다 크거나 같은 값들은 모두 pop해서 모노톤 스택을 유지하고
자기 자신보다 작은 값 중 가장 가까이(stack의 특성 후입선출)에 있는 인덱스의 번호를 알아 낼 수 있다.
왼쪽에서 시작하여 left[]를, 오른쪽에서 시작하여 right[]를 구할 수 있다.
그림설명
예시로 left 배열을 구하는 로직을 확인해보자
스택에 있는 인덱스의 높이 값이 자신보다 작으면, 이 left[현재] = stack.peek() 가 됨
스택안에서 자신의 hight보다 높은 값이 있으면 pop
최종 결과
- 편의를 위해 N+2의 배열로 선언하고 양끝 0, N+1 인덱스는 Height의 값이 없다(0)이다.
즉, 진짜 값이 있는 인덱스는 1~N 이다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class 히스토그램 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// 배열 선언과 초기화
int[] left = new int[N + 2];
int[] right = new int[N + 2];
int[] height = new int[N + 2];
left[N + 1] = N + 1;
right[N + 1] = N + 1;
// 입력과 left monotoneStack
Stack<Integer> monotoneStack = new Stack<>();
monotoneStack.push(0);
for (int now = 1; now <= N; now++) {
height[now] = Integer.parseInt(br.readLine());
if (height[now] == 0) {
monotoneStack.clear();
monotoneStack.push(now);
continue;
}
if (height[monotoneStack.peek()] < height[now]) { // 현재값이 이전 값보다 크면
monotoneStack.push(now);
left[now] = now - 1;
continue;
}
while (height[monotoneStack.peek()] >= height[now]) { // 모노톤 스택 유지
monotoneStack.pop();
}
left[now] = monotoneStack.peek();
monotoneStack.push(now);
}
// max로 answer 구하기 && right monotoneStack
monotoneStack.clear();
long answer = 0;
for (int now = N + 1; now >= 0; now--) {
if (height[now] == 0) { // 0일때 스택 초기화 및 해당 인덱스 push
monotoneStack.clear();
monotoneStack.push(now);
continue;
}
if (height[monotoneStack.peek()] < height[now]) { // 현재값이 이전 값보다 크면
monotoneStack.push(now);
right[now] = now + 1;
answer = Math.max(answer, (long) (right[now] - left[now] - 1) * height[now]);
continue;
}
while (height[monotoneStack.peek()] >= height[now]) { // 모노톤 스택 유지
monotoneStack.pop();
}
right[now] = monotoneStack.peek();
monotoneStack.push(now);
// 정답 구하기
answer = Math.max(answer, (long) (right[now] - left[now] - 1) * height[now]);
}
System.out.println(answer);
}
}
시간복잡도를 단축 시키기 위해 2번의 탐색(N * 2)으로 정답을 도출했다.
첫번째 탐색: 값을 입력받고 left[] 구하기
두번째 탐색: right[]구하기, 넓이를 구해서 정답 도출하기
히스토그램에서 가장 큰 직사각형
문제 출처: https://www.acmicpc.net/problem/6549
6549번: 히스토그램에서 가장 큰 직사각형
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤
www.acmicpc.net
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class 히스토그램에서가장큰직사각형 {
private static StringBuilder sb = new StringBuilder();
private static int N;
private static String[] split;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
split = br.readLine().split(" ");
if (split[0].equals("0")) {
break;
}
N = Integer.parseInt(split[0]);
getAnswer();
}
System.out.println(sb);
}
private static void getAnswer() {
int[] left = new int[N + 2];
int[] right = new int[N + 2];
// 맨 끝값 초기화
left[N + 1] = N + 1;
right[N + 1] = N + 1;
// height 초기화
int[] height = new int[N + 2];
for (int i = 1; i <= N; i++) {
height[i] = Integer.parseInt(split[i]);
}
// 입력과 left monotoneStack
Stack<Integer> monotoneStack = new Stack<>();
for (int now = 0; now <= N; now++) {
if (height[now] == 0) {
monotoneStack.clear();
monotoneStack.push(now);
continue;
}
if (height[monotoneStack.peek()] < height[now]) { // 현재값이 이전 값보다 크면
monotoneStack.push(now);
left[now] = now - 1;
continue;
}
while (height[monotoneStack.peek()] >= height[now]) { // 모노톤 스택 유지
monotoneStack.pop();
}
left[now] = monotoneStack.peek();
monotoneStack.push(now);
}
// right monotoneStack 과 answer 구하기
monotoneStack.clear();
long answer = 0;
for (int now = N + 1; now >= 0; now--) {
if (height[now] == 0) { // 0일때 스택 초기화 및 해당 인덱스 push
monotoneStack.clear();
monotoneStack.push(now);
continue;
}
if (height[monotoneStack.peek()] < height[now]) { // 현재값이 이전 값보다 크면
monotoneStack.push(now);
right[now] = now + 1;
answer = Math.max(answer, (long) (right[now] - left[now] - 1) * height[now]);
continue;
}
while (height[monotoneStack.peek()] >= height[now]) { // 모노톤 스택 유지
monotoneStack.pop();
}
right[now] = monotoneStack.peek();
monotoneStack.push(now);
// 정답 구하기
answer = Math.max(answer, (long) (right[now] - left[now] - 1) * height[now]);
}
sb.append(answer).append("\n");
}
}