[백준] 1725번 히스토그램 자바

문제 (스택)

 

1725번: 히스토그램

 

 

문제 풀이

 

문제 풀이에 대한 논리가 많이 어려웠다. 세그먼트 트리를 이용해서도 많이 푸는 방식인 것 같은데 나는 세그먼트 트리에 대해서 잘 몰라서 만만한(?) 스택으로 풀기로 했다.

 

다른 블로그 글들에 그림 포함해서 설명이 잘 나와있어서 알고리즘은 내가 보기 편한대로 다시 정리해보자면,

우선 히스토그램 순서대로 반복문을 실행하면서 높이가 증가하다가 감소하는 부분을 유의해야 한다. 왜냐하면 높이가 감소하는 순간 바로 그 전까지의 막대로 만들 수 있는 직사각형은 끝이기 때문이다. 추후 다시 같은 길이의 막대가 나온다고 해도, 이어지지 않기 때문에 감소하는 순간을 끊어내야 한다.

 

히스토그램(막대)의 반복문을 돌면서

1. 현재 막대의 높이 기준으로 크거나 같은 것만 스택에 넣는다.

2. 이때, 작은 막대를 만나면 그 동안의 막대 스택에서 만들 수 있는 직사각형을 계산해서 답을 갱신한다.

3. 갱신하는 반복 작업 도중에 원래 다음 순서의 막대 높이보다 꺼내온 스택값이 작을경우 계산 중지한다. (스택에 남겨둠)

  → 왜? 멈춘 스택의 막대 앞까지는 다음에 이어서 직사각형을 만들 수 있기 때문에

4. 이 과정을 반복

 

❓스택에 높이값이 아닌 index값을 넣는 이유

: 증가, 감소, 증가, 감소가 반복되므로 예전에 스택에 들어와있던 막대까지 추후 계산할 때 사용하려면 인덱스로 계산해야 하기 때문에

 

❓높이 배열의 크기 N+2인 이유

: 시작을 0높이로 하여 맨 앞 높이까지 쭉 계산할 수 있도록, 마지막도 0으로 하여금 마지막까지 스택에 남는 것들을 처리하기 위해

 

 

소스 코드

 

public class b_1725 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());	//히스토그램 개수
		int[] height = new int[N+2];			//히스토그램 높이
		
		long answer = 0;
		Stack<Integer> stack = new Stack<>();		//히스토그램 인덱스 담을 스택

		height[0] = 0;	//맨 첫번째 히스토그램까지 포함해서 계산할 때 편리하게
		height[N] = 0;	//반복문 마지막에 스택에 남은 애들을 계산해주기 위해
		
		for(int i = 1; i <= N; i++) 
			height[i] = Integer.parseInt(br.readLine());

		stack.push(0);
		
		for(int i = 1; i <= N+1; i++) {
			while(!stack.isEmpty()) {
				int top = stack.peek();
				
				if(height[top] <= height[i])
					break;
				
				stack.pop();
				answer = Math.max(answer, height[top] * (i-stack.peek()-1));
			}
			
			stack.push(i);
		}
		
		System.out.println(answer);

	}

}