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

스택으로 풀 수 있는 정답률 24퍼센트의 히스토그램에서 가장 큰 직사각형 문제이다.

 

n개의 직사각형이 있고 n개의 직사각형으로 만들 수 있는 가장 큰 직사각형의 넓이를 출력하면 되는 문제이다.

n제한이 100,000이기 때문에 모든 경우를 해보는 O(n^2)의 방법은 시간 초과이다.

스택을 활용한다면 O(n)만에 문제를 풀 수 있다.

 

문제를 푸는 키포인트는

직사각형의 번호를 스택에 높이를 기준으로 오름차순으로 넣어준다는 점이다.

 

문제를 푸는 과정을 설명하자면

0부터 n-1까지의 for문을 돌면서

만약 i번째 직사각형의 높이가 스택에 가장 윗부분 직사각형의 높이보다 낮다면

가능한 넓이를 구하면서 가장 큰 값을 찾아낸다.

마지막으로 스택에 남아있는 것들도 처리해준다

 

i는 현재 위치 즉 오른쪽 위치를 나타내고 stack.peek()은 왼쪽 위치를 나타낸다.

스택에는 높이 오름차순으로 직사각형의 번호가 들어가므로

스택에 마지막에있는 직사각형의 높이를 기준으로 너비를 계산하며 넓이를 구한다.

스택이 빌때까지 pop 해주며 직사각형의 높이와 가능한 너비를 계산해서 가장 큰 넓이를 찾는다.

 

이해하기 굉장히 어려운 문제이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Q6549 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            int n = Integer.parseInt(st.nextToken());
            if(n == 0) break;
            long [] a = new long[n];
            for(int i=0; i<n; i++) {
                a[i] = Long.parseLong(st.nextToken());
            }
            Stack<Integer> s = new Stack<>();
            long ans = 0;
            for(int i=0; i<n; i++) {
                while(!s.isEmpty() && a[s.peek()] > a[i]) {
                    Long height = a[s.pop()];
                    int width = i;
                    if(!s.isEmpty()) {
                        width = i-s.peek()-1;
                    }
                    if(ans < width * height) {
                        ans = width * height;
                    }
                }
                s.push(i);
            }
            while(!s.isEmpty()) {
                long height = a[s.pop()];
                int width = n;
                if(!s.isEmpty()) {
                    width = n-s.peek()-1;
                }
                if(ans < width * height) {
                    ans = width * height;
                }
            }
            System.out.println(ans);
        }
    }
 
}

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

똑같은 문제이다.