[JAVA] 백준 6549 : 히스토그램에서 가장 큰 직사각형

문제

6549번: 히스토그램에서 가장 큰 직사각형

 

해결 방법

처음에 이해가 잘 되지않아서 다른 블로그를 참고해서 풀었다.

참고한 블로그 : iamheesoo.github.io/blog/algo-boj6549

 

스택으로 문제를 풀어나가는 방식이 이해하기 편해서 사용했다.

문제에 있는 예시를 살펴보면

이와 같은 그림이 있다. 각 가로 길이가 1이고 세로 길이가 입력으로 주어지는 직사각형들이 연달아서 존재하고 이 중에서

가장 넓이가 큰 직사각형을 찾아내야하는데, 위 예제에서는 우측의 빗금쳐진 직사각형이 가장 큰 넓이를 가진 직사각형이 된다.

 

그럼 이와 같은 값을 어떻게 구할 것인가.

가장 먼저 든 생각은 왼쪽부터 차례로 가장 큰 직사각형을 찾아나가는 방식이다.

이 방식을 구현하기 위해서 스택을 사용한다.

 

코드에서 가장 큰 직사각형을 찾아가는 과정을 그림으로 보여주려 한다.

처음 반복문에 들어가면 스택이 비어있기 때문에 스택에 제일 처음 idx 값인 0이 들어가게 된다.

다음 반복에서 스택에 값이 있고 1번 째 인덱스의 값이 1로 2인 처음 값보다 작기 때문에 스택에 있던 0을 꺼낸 뒤에

길이 값을 구해서 검게 칠해진 부분의 넓이를 처음으로 계산한다.

그래서 max에 검게 칠해진 부분의 넓이인 2가 들어간다.

그 뒤 1이 스택에 들어가서 스택에는 1만 존재한다.

 

그렇게 반복문이 진행되다가 i가 4일 때 stack.peek()의 값이 자신보다 크기 때문에 while문 안의 넓이 구하는 식을 실행시키게 된다.

그래서 두번 째로 구해지는 넓이는 위와 같은 검은 직사각형이 되고 넓이가 max에 담겨있는 2보다 큰 5이기 때문에 5로 값이 바뀐다.

그리고 while의 조건을 아직 만족하기 때문에 한번 더 루프가 돌아가게 되는데, 다음 루프에서는

위와 같은 넓이를 구하게 되고 max보다 큰 값이기 때문에 다시 값이 바뀐다.

그리고 계속 루프가 진행되서 끝나게 되지만, 스택에 아직 값들이 1, 4, 5, 6 순서대로 총 4개가 남아있어 그 이후에 있는 반복문을 다시 실행시키게 된다.

앞에 있는 반복문과는 가로의 길이를 구하는 공식이 살짝 다르다.

그래서 마지막 while문을 통과하면 그림 순서대로의 직사각형의 넓이를 확인한다.

위 그림 순서대로 넓이를 체크하고 max 값과 비교해서 가장 큰 값을 출력하게 된다.

그래서 총 7개의 값이 주어졌을 때 7개의 직사각형을 만들어서 체크하게 되었고,

총 N의 시간의 소요된다고 볼 수 있다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		while (true) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			if (n == 0) break;
			
			int height[] = new int[n];
			for (int i = 0; i < n; i++) {
				height[i] = Integer.parseInt(st.nextToken());
			}
			
			Stack<Integer> stack = new Stack<>();
			long max = Long.MIN_VALUE;
			
			for (int i = 0; i < n; i++) {	
					while (!stack.isEmpty() && height[stack.peek()] > height[i]) {
						int idx = stack.pop();
						int width = stack.isEmpty() ? i : i - stack.peek() - 1;
						max = Math.max(max, (long)width * height[idx]);
					}
					stack.push(i);
			}
			
			while (!stack.isEmpty()) {
				int idx = stack.pop();
				int width = stack.isEmpty() ? n : n - stack.peek() - 1;
				max = Math.max(max, (long)width * height[idx]);
			}
			sb.append(max + "\n");
		}
		System.out.println(sb);
	}
}