문제 풀이

이번 주말에 코딩테스트를 쳤는데 히스토그램과 유사한 느낌의 문제가 나와서 한번 풀어 봤다.
도저히 내 머리로는 풀진 못하고 다른분들의 글들을 참고해서 풀었다.

분할 정복방식과 스택을 이용한 방식이있는데 나는 스택을 이용한 방식으로 풀어봤다.

배열을 처음부터 순회하면서 현재 배열의 값보다 스택의 탑이 작아질 때까지 pop을 하고
현재 배열의 값이 스택의 탑보다 클 때 push를 해주는 방식이다.

참고로 스택에는 인덱스의 값이 들어가기 때문에 대소 비교는 arr[스택의 탑] >= arr[i] <- 이런식으로 해야한다.
높이는 현재 스택의 탑으로 두고, 너비는 스택에 들어있는 인덱스를 이용해서 현재 확인하려는 위치에서 얼만큼 떨어져 있는지 얻어내고 높이와 너비를 곱하면 그 넓이가 나온다.

핵심은 현재 배열 값보다 스택의 값이 클 때 pop을 해주면서 넓이를 갱신한다는 것.

문제 링크

boj/1725

소스코드

PS/1725.java

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

    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        public static void main(String[] args) throws IOException {
            int n = Integer.parseInt(br.readLine());
            int []arr= new int[n];
            Stack<Integer> st = new Stack<>();
            for(int i=0;i<n;i++)
                arr[i] = Integer.parseInt(br.readLine());
            int ans = 0 ;
            for(int i=0;i<n;i++)
            {
                while(!st.empty() && arr[st.peek()] >= arr[i])
                {
                    int height = arr[st.pop()];
                    int width = st.empty() ? i : i -1 - st.peek();
                    ans = Math.max(ans, height * width);
                }
                st.add(i);
            }
            while(!st.empty())
            {
                int height = arr[st.pop()];
                int width = st.empty() ? n : n - 1 - st.peek();
                ans = Math.max(ans, height * width);
            }
            bw.write(Integer.toString(ans));
            bw.flush();
        }
    }