[BOJ 백준] 히스토그램에서 가장 큰 직사각형(6549) Java

링크 : https://www.acmicpc.net/problem/6549

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

 

문제 설명 : 

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 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) 어떻게 풀 것인가?

N이 10만이다. 10만개의 직사각형이 주어지고 이 직사각형 그림에서 최대 넓이의 직사각형을 구해야한다.

 

N이 10만이므로 시간복잡도 N 또는 N logN의 접근이 필요하다.

 

크게 2가지로 접근이 가능하다.

 

① Stack 자료구조의 특성을 이용한 방법 (시간복잡도 N)

    - Stack은 FILO(First In, Last Out)의 구조를 가진다. 이를 직사각형의 넓이를 구하는데 활용할 수 있다.

      (높이가 낮은 놈을 Stack 아래에 묵혀놓고, 높이가 큰 녀석이 나올때마다 pop 해서 넓이를 구하는 방식)      

      자세한 로직은 아래 코드 참고.

 

② 세그먼트트리를 활용한 방법  (시간복잡도 N logN)

    - 세그먼트 트리 노드에 최솟값의 인덱스를 저장하는 방법

 

이 포스트에서는 ① Stack 자료구조의 특성을 이용한 방법으로 푸는 코드를 다뤘다. (아래 Java 코드 참고)

 

② 세그먼트트리를 활용한 방법은 이 곳에 잘 정리가 되어있다.

https://blog.naver.com/occidere/221057769152

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

 

 

2) 시간복잡도

10만의 높이를 input받으면서 모든 로직을 처리한다.

N의 시간복잡도 내부에 while문 로직이 끼어있어 정확한 시간 산정은 어렵지만,

Stack에서 pop된 데이터는 절대 push 될 일이 없기 때문에

결국 상수 * N에 가까운 시간복잡도가 발생될 것으로 예상.

(Java 기준 -  424ms)

 

3) 공간복잡도

int 10만개 * 2개 배열 = 약 int 20만개 배열이 든다.

4Bytes (int) * 20만 = 1MBytes 미만으로 여유있다. 

 

4) 풀면서 놓쳤던점

아무 생각없이 ans를 int로 해버림.

 

5) 이 문제를 통해 얻어갈 것

스택(Stack) 자료구조의 활용.

기회가 된다면 세그먼트트리로 풀어보기

 

Java 코드 : 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

// 히스토그램에서 가장 큰 직사각형 백준 6549
public class Main {
		
	static class info{
		int id, height;		// 위치, 높이 

		public info(int id, int height) {
			this.id = id;
			this.height = height;
		}
	}
	
	static int N, input, wp;		// N 줄의 개수, input 입력받는 수, wp 스택의 writing pointer
	static long ans;				// ans 정답
	static info[] stack;			// stack 스택
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st; 
		
		for ( ; ; ) {
			st = new StringTokenizer(br.readLine());
			// N 입력
			N = Integer.parseInt(st.nextToken());
			// N이 0이면 프로그램 종료
			if(N==0) break;
			
			// 초기화 Stack 초기화, pointer, answer 0으로 만들기
			stack = new info[N];
			wp = 0;
			ans = 0;
			
			// 1. 입력받는 직사각형의 높이가 Stack의 첫번째 수보다 작을 경우
			//     → Stack에서 더 작은 수가 나올때까지 빼면서 넓이 구해주고 갱신
			// 2. 입력받는 직사각형의 높이가 Stack의 첫번째 수보다 클 경우 
			//     → Stack에 추가 (더 큰 넓이가 될 가능성이 있으므로 추가)
			for(int i=0; i<N; i++) {
				int tId = i;		// 임시 id는 현재 위치 
				input = Integer.parseInt(st.nextToken()); 
			
				// 1. 입력받는 직사각형의 높이가 Stack의 첫번째 수보다 작을 경우
				//     → Stack에서 더 작은 수가 나올때까지 빼면서 넓이 구해주고 갱신
				while(wp > 0 && stack[wp-1].height > input) {
					long tmpSize = (long)(i - stack[wp-1].id) * stack[wp-1].height;
					ans = ans > tmpSize ? ans : tmpSize;
					tId = stack[wp-1].id;		// 임시 id를 앞으로 당김
					wp--;
				}
								
				// 2. 입력받는 직사각형의 높이가 Stack의 첫번째 수보다 클 경우 
				//     → Stack에 추가 (더 큰 넓이가 될 가능성이 있으므로 추가)
				stack[wp] = new info(tId, input);
				wp++;
				
			}
			// 3. 마지막으로 Stack에 남아있는 애들 쭉 빼면서 넓이 확인
			while(wp > 0) {
				long tmpSize = (long)(N - stack[wp-1].id) * stack[wp-1].height;
				ans = ans > tmpSize ? ans : tmpSize;
				wp--;
			}
			// 정답출력
			bw.write(String.valueOf(ans)+"\n");
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}