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

 

 

https://13months.tistory.com/100

[백준] 1725 히스토그램 - Java

 

위의 문제를 풀고 오니 이번 문제는 덤으로 같이 주는 느낌이였다.

입력 방법의 차이가 있을 뿐 풀이법은 같다.

 

 

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();

		while (true) { // while 루프의 시작

			String[] temparr = sc.nextLine().split(" ");

			int[] heightarr1 = new int[temparr.length];

			for (int i = 0; i < heightarr1.length; i++) {
				heightarr1[i] = Integer.parseInt(temparr[i]);
			} // 높이 정보 입력. 배열에다가 입력해준다.

			if (heightarr1[0] == 0 && heightarr1.length == 1) {
				break;
			} // 탈출구
			
			int[] heightarr = new int[heightarr1.length-1];
			
			for(int i=0; i<heightarr.length; i++) {
				heightarr[i] = heightarr1[i+1];
			}
			
		
			
			
			// 여기까지는 입력부분 
			
			Stack<Integer> st = new Stack<>();

			long maxvalue = 0;

			for (int i = 0; i < heightarr.length; i++) {
				// 스택에는 인덱스를 담고, heightarr에는 높이 정보를 담는다.
				while (st.isEmpty() == false && heightarr[st.peek()] >= heightarr[i]) {
					// 스택이 비어있지 않고 지금 탐색하는 막대의 높이가 바로 전에 탐색한 막대의 높이보다 작거나 같으면 (이전이 더 크면)
                    // 과거 막대들을 pop 하면서 넓이를 구한다. 
                    //이때 pop 하는 막대들의 높이는 heightarr[i] 보다 작거나 같은걸로..
                    
					long height = heightarr[st.pop()];
                    // 높이를 바로 전에 탐색한 막대의 높이로 설정하고 pop 진행

					long width = 0;

					if (st.isEmpty()) { 
                    // pop한 다음에 스택이 비어있으면, 즉 0~ i-1 가 폭이 된다.
						width = i;
					} else {
						width = i - 1 - st.peek(); 
                        // pop한 다음 스택이 비어있지 않으면 최댓값을 계속 갱신시킨다. 
                        // 체인의 폭은 i-1-가장최근인덱스
					}
					maxvalue = Math.max(maxvalue, width * height);
				}
				st.push(i); 
                // 스택이 비어있을때까지 수행하고 비어있으면 인덱스를 넣어준다.
			}
			while (st.isEmpty() == false) {
				long height = heightarr[st.pop()];
				long width = 0;
				if (st.isEmpty()) {
					width = heightarr.length;
				} else {
					width = heightarr.length - 1 - st.peek();
				}

				maxvalue = Math.max(maxvalue, width * height);
			}

			sb.append(maxvalue).append("\n");

		} // while 루프의 끝

		System.out.println(sb);
	}
}