백준 1725 히스토그램 Java 풀이

 heights 를 이중순회하면서 height[j] < height[i] 일때까지 순회하여 height[i] * j 를 직사각형의 넓이

문제

각 칸의 넓이가 동일한 히스토그램의 높이 값이 주어진다. 이 히스토그램에서 가장 넓은 사각형을 만들었을 때 그 넓이를 출력하라

시간 제한: 0.7초

데이터 크기:  1 <= N < 100,000

 

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

 

접근

히스토그램의 높이값 배열을 heights 라고 하자

기본적인 아이디어는 heights 를 하나의 방향으로 순회할때  height[i] 보다  height[i+1] 이 작으면 더이상 height[i] 높이의 사각형을 만들 수 없다는 것이다.

부르트포스

따라서 부루트포스 접근으로 heights 를 이중순회하면서 height[j] < height[i] 일때까지 순회하여 height[i] * j 를 사각형의 넓이로 하고 이 넓이를 모두 비교하여 가장 큰 것을 출력할 수 있겠다.

하지만 이 접근의 시간 복잡도는 O((n * n)) 이다. 1초에 2억번 연산을 한다고 생각하면 (100,000^{2}) 은가볍게 2억은 넘기 때문에 시간 제한 0.7초를 초과하게 된다.

높이 자체를 저장하기((Deque))

시간 제한을 생각한다면 O((n)) 의 시간복잡도를 갖는 접근을 생각해야한다.

heights 를 한방향으로 순회하면서 Deque 자료구조를 활용하는 방법을 이용할 수 있겠다.

기본적인 아이디어는 "height[i] 보다  height[i+1] 이 작으면 더이상 height[i] 높이의 사각형을 만들 수 없다" 는 것에 기반하여 다음과 같은 풀이 과정을 생각해봤다.

• Step1: Deque.last() <= heights[i] 이면 Deque 에 있는 것들과 같이 사각형을 만들 수 있는 높이이므로 Deque.addLast((heights[i])) 를 한다.
• Step2: Deque.last() > heights[i] 이면 이후에 등장하는 heights[i] 와 Deque 에 저장된 높이는 사각형을 만들 수 없으므로  Deque.isEmpty() 가될 때까지 저장된 높이와  각 높이들의 넓이가 동일하다는 가정을 통해 "사각형의 넓이를 계산" 한다.

다만 이러한 접근에는 맹점이 있는데

Deque.last() > heights[i] 조건이 충족하여 Deque 내부에 있는 높이들을 이용해서 직사각형의 넓이는 계산되지만 heights[i] 를 기준으로 Deque 의 내부 높이를 활용하여 직사각형의 넓이를 계산하는 작업이 수행되지 않기 때문이다.

 

높이 인덱스를 저장하기 ((Stack))

위의 맹점을 높이 자체를 저장하기 보다는 높이의 인덱스를 저장하는것으로 더 효율적인 알고리즘을 만들 수 있다.

기본적인 아이디어는 "height[i] 보다  height[i+1] 이 작으면 더이상 height[i] 높이의 사각형을 만들 수 없다" 로 동일하다.

 

풀이

부르트포스 -> 시간초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n;
    static int[] heights;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        heights = new int[n];

        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            heights[i] = Integer.parseInt(br.readLine());
        }

        for (int i = 0; i < n; i++) {
            int currentHeight = heights[i];

            // 좌측 탐색: 현재 막대보다 높거나 같은 첫 번째 막대 찾기
            int left = i;
            while (left >= 0 && heights[left] >= currentHeight) {
                left--;
            }
            left++; // 현재 막대가 시작할 수 있는 첫 인덱스

            // 우측 탐색: 현재 막대보다 높거나 같은 첫 번째 막대 찾기
            int right = i;
            while (right < n && heights[right] >= currentHeight) {
                right++;
            }
            right--; // 현재 막대가 끝날 수 있는 마지막 인덱스

            // 너비 계산: (right - left + 1)
            int width = right - left + 1;
            int area = width * currentHeight;

            // 최대 넓이 갱신
            maxArea = Math.max(maxArea, area);
        }
        System.out.println(maxArea);
    }
}

 

높이 자체를 저장하기 ((Deque)) -> 잘못된 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    static int n;
    static int[] heights;

    public static void main(String[] args) throws IOException {
        // 입력 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = Integer.parseInt(br.readLine());
        }

        // 최대 직사각형 넓이 계산
        Deque<Integer> deque = new LinkedList<>();
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && deque.getLast() > heights[i]) {
                int nowArea = deque.getFirst() * deque.size();
                deque.removeFirst();
                maxArea = Math.max(maxArea, nowArea);
            }
            deque.addLast(heights[i]);
        }
        
        while (!deque.isEmpty()) {
            int nowArea = deque.getFirst() * deque.size();
            deque.removeFirst();
            maxArea = Math.max(maxArea, nowArea);
        }
        System.out.println(maxArea);
    }
}

 

높이 인덱스를 저장하기 ((Stack)) -> 제일 나은 접근

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    static int n;
    static int[] heights;

    public static void main(String[] args) throws IOException {
        // 입력 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        heights = new int[n];

        for (int i = 0; i < n; i++) {
            heights[i] = Integer.parseInt(br.readLine());
        }

        // 직사각형 최대넓이 계산
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;

        while (i < n) {
            if (stack.isEmpty() || heights[stack.peek()] <= heights[i]) { // 현재 막대가 스택의 마지막 막대보다 크거나 같으면 스택에 추가
                stack.push(i++);
            } else { // 현재 막대가 스택의 마지막 막대보다 작으면 넓이 계산
                int height = heights[stack.pop()];
                
                // 높이로 만들 수 있는 직사각형의 넓이 계산 
                // (1) stack 이 비어있다면 index i 좌측에 이번에 pop 한 height 보다 낮은 값이 존재하기 않는다는것을 의미하므로 0 ~ i 번째 인덱스까지가 넓이다. => i
                // (2) stack 이 비어있지 않다면 index i 좌측에 이번이 pop 한 height 보다 낮은 값이 존재하는 것이기 때문에 pop 한 인덱스 기준으로 얼마나 오른쪽으로 이동해야하는지 게산해야한다. 
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
        }

        // 스택에 남아 있는 막대들에 대해 넓이 계산
        while (!stack.isEmpty()) {
            int topIndex = stack.pop();
            int height = heights[topIndex];
            int width = stack.isEmpty() ? n : n - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        System.out.println(maxArea);
    }