[JAVA] BOJ 백준 1725번 - 히스토그램

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1725번: 히스토그램

---

2. 내가 푼 방법

너비를 구하는 게 조금 헷갈리는 문제이다.

 

스택을 이용하는데, push 되는 값이 가장 큰 값이 되도록 저장했다. 그래야 더 작은 값이 들어가기 전에 높이가 가장 긴 직사각형을 구할 수 있기 때문이다. 실제로는 스택에는 가장 큰 값의 인덱스를 저장해 두었는데, 새로 push 할 값(arr[i])이 스택에 들어있는 값보다 작거나 같을 경우에 while문에 진입한다.

 

while 문에 집입 후, 높이는 stack.pop(); 을 하여 찾은 인덱스로 arr 배열에서 값을 찾아오면 된다.

너비는 stack.pop(); 한 높이를 포함하고 있는 총길이를 구해야 하므로, 스택에 들어있는 이전 인덱스(얘가 더 작은 높이를 가짐) + 1에서 현재 push 될 인덱스까지의 길이가 된다. 따라서 (현재 push 될 인덱스) - (스택에 들어있는 이전 인덱스 + 1) 이므로 i - stack.peek() - 1; 이 된다. 만약 스택이 비어있다면 처음부터 현재 push 될 인덱스까지 현재 높이를 포함하고 있는 것이므로 i - 0 - 1 즉, i - 1 이 되는 것이다.

Stack<Integer> stack = new Stack<>();
long result = 0;

for (int i = 1; i <= N; i++) {
    arr[i] = Integer.parseInt(br.readLine());

    while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
        int idx = stack.pop();
        int h = arr[idx];
        int w = (stack.isEmpty()) ? i - 0 - 1 : i - stack.peek() - 1;

        result = Math.max(result, h * w);
    }

    stack.push(i);
}

 

이제 스택에 남은 직사각형 넓이를 구해야 한다. 위에서 했던 설명과 동일하며, 단지 i가 N+1로 바뀐 것뿐이다.

while (!stack.isEmpty()) {
    int idx = stack.pop();
    int h = arr[idx];
    int w = (stack.isEmpty()) ? (N+1) - 0 - 1 : (N+1) - stack.peek() - 1;

    result = Math.max(result, h * w);
}

---

3. 자바 코드

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

class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N + 1];
        Stack<Integer> stack = new Stack<>();
        long result = 0;

        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());

            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                int idx = stack.pop();
                int h = arr[idx];
                int w = (stack.isEmpty()) ? i - 1 : i - stack.peek() - 1;

                result = Math.max(result, h * w);
            }

            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int idx = stack.pop();
            int h = arr[idx];
            int w = (stack.isEmpty()) ? N : (N+1) - stack.peek() - 1;

            result = Math.max(result, h * w);
        }

        bw.write(result+"");

        br.close();
        bw.flush();
        bw.close();
    }
}

---

4. 결과 및 회고

다시 푼 문제인데, 이번에는 제대로 알고 풀어냈다. ㅎㅎ