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

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

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

 

접근 과정 : 

• 주어진 직사각형들을 순회하면서, 현재 i번째 사각형까지 만들 수 있는 직사각형의 넓이를 구하려고 했다.
• 현재 i번째 사각형과 비교해서 가능한 높이의 이전 사각형을 Stack에 담아서 비교하고자 하였다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    히스토그램에서 가장 큰 직사각형 
*/

import java.io.*;
import java.util.*;

public class BOJ6549 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        while (true) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());

            if (n == 0) {
                break;
            }

            long[] h = new long[n];
            for (int i = 0; i < n; i++) {
                h[i] = Long.parseLong(st.nextToken());
            }

            long max = 0;
            Stack<Integer> stack = new Stack();
            for (int i = 0; i < n; i++) {
                while (!stack.isEmpty() && h[stack.peek()] > h[i]) {
                    long before = h[stack.pop()];

                    int width = i;
                    if (!stack.isEmpty()) {
                        width = (i - stack.peek() - 1);
                    }
                    if (max < width * before) {
                        max = width * before;
                    }

                }
                stack.push(i);
            }

            while (!stack.isEmpty()) {
                long before = h[stack.pop()];

                int width = n;
                if (!stack.isEmpty()) {
                    width = (n - stack.peek() - 1);
                }
                if (max < width * before) {
                    max = width * before;
                }
            }

            sb.append(max + "\n");
        }

        System.out.println(sb.toString().trim());

    }
}

 

 

P.S 

이번 문제는 시간초과로 인해 많은 고생을 하였다....

https://www.acmicpc.net/blog/view/12 

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

결국 해당 설명을 보고 다시 접근을 하였고.. 사실상 거의 복붙으로 문제를 해결한 것 같다.ㅜㅜ

 

분리집합으로 해결하는 부분은 나중에 한번더 이해하고 해결해보아야겠다.