sm 기술 블로그

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

문제/백준_자바

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

sm_hope 2022. 8. 6. 15:17
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

문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1,

hooongs.tistory.com

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

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이 출력값이 되는 것이다.

Comments