[백준] 💧 1725 히스토그램

📌 난이도

💧 Platinum 5

📌 문제

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

📌 풀이

저번에 처음으로 소트 라는 플레티넘 문제를 풀고 나서 2번째로 도전해보는 플레티넘 문제였다.

처음 이 문제를 보고 든 생각은 이거 완전탐색 문제인가? 라는 발상이였다.
왜냐하면 최대 넓이를 구하기 위해서는 무조건 나올 수 있는 모든 사각형의 넓이를 구한후, 그 값들을 max 쳐서 구해야 하지 않겠냐는 생각이였다.
그래서 모든 직사각형의 넓이를 어떻게 해야지 시간초과가 뜨지 않을까라고 고민하였다.

일단 시간복잡도를 계산해보니 n = 100000 이므로 o(nlog(n)) ≒ 20,000,000 (0.2초) 가 쓸 수 있는 최대한의 시간이였다.
그래서 for문 을 한번 돌리면서 아무리 커도 log(n) 의 시간복잡도를 가지고 탐색을 해야했다.

이런 고민을 하던 차에 Stack 이라는 힌트를 얻고 나서 갑자기 생각이 번뜩 들었다.
바로 for(int i)문 에서 0~N까지 가면서 stack<Integer[]> 에 그 위치에서의 높이 즉 value 라는 변수와 i 라는 주소값을 넣었다.
다음에 새로 stack에 값을 집어넣을때 이전 값과 비교해서 높이가 더 높으면 그대로 집어넣고, 더 작으면 더 큰 값이 나오거나 빌 때까지 빼면서 뺀 값의 index값 과 현재 index값 의 차이에 높이를 곱해서 max과 Math.max 를 계산해 주었다.
그리고 stack 에 새로 넣는 값은 뺀 값의 index값 에 value 를 더해주었다.

이후 이 모든 과정을 거친 후 stack에는 자동으로 가장 작은 높이가 1개만 남게 된다.
그래서 마지막으로 남은 값과 n을 곱한값을 max 와 비교해서 최대값을 출력해주었다.

이후 다음과 같이 코드가 작성되었다.
플레티넘 문제이지만 생각보다 쉽게 풀려서 좋았다. 😎

📌 Code

package BOJ.DS;

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

public class N1725 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Stack<Integer[]> st = new Stack<>();
        int max = 0;
        st.add(new Integer[]{Integer.parseInt(br.readLine()), 0});
        for (int i = 1; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            if (num > st.peek()[0]) {
                st.add(new Integer[]{num, i});
            } else if (num == st.peek()[0]) {
                //아무것도 안한다.
            } else {
                Integer[] arr = st.pop();
                max = Math.max(arr[0] * (i - arr[1]), max);
                while (!st.isEmpty() && num < st.peek()[0]) {
                    arr = st.pop();
                    max = Math.max(arr[0] * (i - arr[1]), max);
                }
                st.add(new Integer[]{num, arr[1]});
            }
        }
        while (!st.isEmpty()) {
            Integer[] arr = st.pop();
            max = Math.max(arr[0] * (N - arr[1]), max);
        }
        System.out.println(max);
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

📌 추가 예제

[Input]
8
1
2
3
4
5
6
7
8

[Output]
20

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁