172. 6549 (히스토그램에서 가장 큰 직사각형) - 자바

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		while (true) {
			String[] tmpStr = br.readLine().split(" ");
			int n = Integer.parseInt(tmpStr[0]);

			if (n == 0) {
				break;
			}

			int[] h = new int[n];
			for (int i = 1; i < tmpStr.length; i++) {
				h[i - 1] = Integer.parseInt(tmpStr[i]);
			}

			Deque<Integer> queue = new ArrayDeque<>();
			long result = 0;

			for (int i = 0; i < n; i++) {
				while (!queue.isEmpty() && h[queue.peekLast()] >= h[i]) {
					int tmp = queue.pollLast();
					long w = 0;

					if (queue.size() == 0) {
						w = i;
					} else {
						w = i - queue.peekLast() - 1;
					}
					result = Math.max(result, w * h[tmp]);
				}
				queue.add(i);
			}

			while (!queue.isEmpty()) {
				int tmp = queue.pollLast();
				long w = 0;
				if (queue.size() == 0) {
					w = n;
				} else {
					w = n - queue.peekLast() - 1;
				}
				result = Math.max(result, w * h[tmp]);
			}
			sb.append(result).append("\n");
		}
		System.out.print(sb);
	}
}

문제요약

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형으로 직사각형이 가장 큰 값을 구하라.

설명

이 문제는 스택, 분할정복, 세그먼트 트리등을 이용하여 풀 수 있다.

스택이 제일 간단하고 이해하기 쉽기 때문에 스택을 이용하여 풀이를 진행하겠다.

 

아래 사이트를 참고했다.

https://hooongs.tistory.com/330

[백준6549번] 히스토그램에서 가장 큰 직사각형 / Python3

다음과 같은 값이 주어졌다.

3번째, 4번째를 이용해서 만든 직사각형 크기가 8로 가장 큰 직사각형에 해당한다.

이를 스택을 이용해서 풀어야 한다.

 

1차

			for (int i = 0; i < n; i++) {
				while (!queue.isEmpty() && h[queue.peekLast()] >= h[i]) {
					int tmp = queue.pollLast();
					long w = 0;

					if (queue.size() == 0) {
						w = i;
					} else {
						w = i - queue.peekLast() - 1;
					}
					result = Math.max(result, w * h[tmp]);
				}
				queue.add(i);
			}

(1) 현재 i 는 0

먼저 스택에 0번째 인덱스에 해당하는 2를 넣는다.

 

(2) 현재 i 는 1

스택에 들어있던 '2'가 새로 들어온 '1'보다 크기 때문에 2를 빼고 result 후보군에 넣게 된다.

이후 스택이 비어있으므로 1을 집어 넣는다.

 

(3) 현재 i 는 2

4가 1보다 크기 때문에 stack에 값을 넣고 다음으로 넘어간다.

 

(4) 현재 i 는 3

5가 4보다 크기 때문에 stack에 값을 넣고 다음으로 넘어간다.

 

(5) 현재 i는 4

 

4번째의 값은 1이다.

따라서 2번째, 3번째는 pop을 통해 값을 빼고 계산을 진행해야한다.

계산된 값과 그전에 있던 result를 비교해서 둘 중 더 큰 값을 result에 저장한다.

 

(6) 현재 i 는 5

3이 1보다 크기 때문에 stack에 값을 넣고 넘어간다.

 

(7) 현재 i 는 6

3이 1보다 크기 때문에 stack에 값을 넣고 넘어간다.

 

2차

			while (!queue.isEmpty()) {
				int tmp = queue.pollLast();
				long w = 0;
				if (queue.size() == 0) {
					w = n;
				} else {
					w = n - queue.peekLast() - 1;
				}
				result = Math.max(result, w * h[tmp]);
			}
			sb.append(result).append("\n");
		}
		System.out.print(sb);

stack 에 넣는것은 끝났다 하지만 아직 스택에 값이 있으므로 2차에서는 스택을 비우는 작업을 통해서 result가 더 큰 것이 있다면 그 값을 result에 넣을 것이다.

 

계산을 진행해도 8이 가장 크다는 것을 알 수 있고 그 8이 출력값이 되는 것이다.