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

 

 

 

스택에 인덱스를 넣어주고 따로 배열을 설정해 배열에는 직사각형의 높이에 대한 정보를 넣었다.

넓이를 구하는 과정은 이전에 탐색한 직사각형의 높이가 현재 탐색하고 있는 직사각형의 높이보다 높을 때이다.

이 때를 기준으로 지금까지 쌓아온 스택 인덱스에 해당하는 직사각형의 높이들을 현재 탐색하고 있는 높이보다 작거나 같은 높이들을 대상으로 하나씩 pop해주며 넓이를 계산한다.

 

차례차례 pop을 진행해주며 넓이를 구해주는데, 이 과정은 코드를 참고하자.

 

이후 pop 과정 수행 후 스택에 남아있는 원소들에 대해서도 처리해주기 위해 다시 pop을 수행한 후 출력해줬다.

 

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		long maxvalue = 0;
		int N = sc.nextInt();
		int[] heightarr = new int[N];
		Stack<Integer> st = new Stack<>();

		for (int i = 0; i < heightarr.length; i++) {
			heightarr[i] = sc.nextInt();
		}
		
		
		// 스택에 체인을 걸어서 구해준다.
		// 스택에는 인덱스, heightarr에는 높이정보
		
		for (int i = 0; i < heightarr.length; i++) {
			while (st.isEmpty() == false && heightarr[st.peek()] >= heightarr[i]) {
				// 체인을 설정할 때 지금 탐색하는 막대 높이보다 바로전에 탐색한 막대 높이보다 커야함
				long height = heightarr[st.pop()];
				// 체인 형성이 안됐을때는 pop하면서 높이 구함
				long width = 0;
				if (st.isEmpty()) {
					width = i;
				} else {
					width = i - 1 - st.peek();
				}
				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);
		}
		
		System.out.print(maxvalue);

	}
}

 

 

이 문제는 두시간동안 풀다 방향을 아예 잘못 설정한 것 같아 다른 블로그 글을 참고해서 풀었다.

 

https://st-lab.tistory.com/255