백준 17245 자바 - 히스토그램 (BOJ 17245 JAVA)

문제 : boj17245

 

 

  일단 단순화 시켜서 생각해보기 위해 좌측부터 우측으로 점차 증가하는 형태와 점차 감소하는 형태를 나눠서 생각해봤다.

 

1. 우선 높이(h)가 같거나 증가하는 경우이다.

이전과 비교해서 값이 같거나 증가하고 있다면, 아직까지는 넓이를 계산하는 것이 의미가 없다. n개를 모두 입력받았거나, 이후 감소하는 구간을 만나기 전까지는 넓이를 계산하지 않고 있다가 맨 마지막 지점에서만 계산해주면 된다. 직관적으로 맨 마지막 지점을 포함한 상태에서 다음과 같이 이전 높이들을 확인하면 될 것임을 예상할 수 있다.

 

 

즉, 높이가 동일하거나 증가하는 경우 맨 마지막 지점에서 이전 지점 모두 중 의미가 있는 넓이는 모두 계산할 수 있다.

 

 

2. 다음은 높이(h)가 감소하는 경우이다.

이번엔 좌측에서 우측으로 진행할 때, 언제 넓이를 확인해야 할까? 증가하는 경우와는 반대로 매번 확인해야 한다. n을 맨 마지막 지점을 포함한 채로는 그 이전의 넓이를 계산할 수 없다. 즉 n이 진행됨에 따라 다음과 같이 살펴봐야 한다.

 

 

 

3. '1', '2'를 통합해서 로직을 만들자.

  로직을 정리하면, [ 동일하거나 증가하는 동안은 넓이를 체크하지 않으며 이전 높이들만 기록해두고, 그 끝(감소하거나 히스토그램이 끝남)을 만날 때 마지막 지점에서 전부 계산한다! ]가 된다.

 

  이전 높이를 가져올 수 있도록 스택 자료구조를 사용한다. 그리고 각 n 지점을 순회하며 높이를 입력받고,

3.1 스택이 비었거나 높이가 이전과 동일하거나 증가한다면 넓이를 계산하지 않고 스택에 넣는다.

 

3.2 높이가 이전보다 낮아졌다면, 현재 스택의 상태는 '1'에서 넣었던 동일하거나 증가하는 상태일 것이다. 따라서 스택이 비거나, 현재 높이보다 큰 부분까지 빼면서 넓이를 계산한다. 즉, 위에서 그려뒀던 이미지 중 높이가 같거나 증가하는 동안에 해당하는 로직을 수행한다. (popStackUntilH 함수) 그 후에 현재 지점의 높이를 다시 스택에 넣는다.

 

* 주의 : 감소할 때 스택 전체를 빼지않고 현재 높이보다 큰 부분까지만 빼는 이유는 다음과 같은 경우를 처리하기 위해서이다.

 

3.3 히스토그램의 끝을 만났을 때에도 동일하게 수행한다. (38line) -> 다만 이 때는 남은건 전부 빼야 하므로 현재 높이가 0이라고 치면 모두 뺄 수 있다. (curIdx == n ? 0 : arr[curIdx]; 부분)

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Stack;

public class Main {
    static int[] arr;
    static long max;
    static int n;

    private static void popStackUntilH(Stack<Integer> stk, int curIdx) {
        int curHeight = curIdx == n ? 0 : arr[curIdx];
        while (!stk.isEmpty() && arr[stk.peek()] > curHeight) {
            int h = arr[stk.pop()];
            int w = stk.isEmpty() ? curIdx : curIdx - stk.peek() - 1;
            max = Math.max(max, 1l*h*w);
        }
    }

    private static void solution() throws Exception {
        StringBuilder sb = new StringBuilder();
        n = nextInt();
        arr = new int[n];
        max = 0l;

        Stack<Integer> stk = new Stack<>();
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
            int curH = arr[i];
            if (stk.isEmpty() || arr[stk.peek()] <= curH) {
                stk.push(i); continue;
            }

            popStackUntilH(stk, i);
            stk.push(i);
        }
        popStackUntilH(stk, n);
        sb.append(max).append('\n');

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        solution();
    }

    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    private static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    private static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}