알고리즘/백준

[백준 1725] 히스토그램 C++

겜도리도리 2023. 12. 4. 21:09
반응형

문제

백준 1725 히스토그램

 

1725번: 히스토그램

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자

www.acmicpc.net

풀이

오름차순 Monotonic Stack을 활용했다.

 

startIdxs(n) 배열을 사용했는데, 이 배열은 i번째 value에 대해, 그보다 작은 값이 그전 원소들 중에서 언제 처음 등장하는지 인덱스를 담고 있는 배열이다. 작은 값이 없다면 0을 담고 있다.

 

예를 들어서 5 3 2 3 5에 대해

startIdxs는 idx순서대로 각각 0, 0, 0, 2, 3이 된다.

넓이를 구할 때는 특정 원소가 빠질 때, 그 원소의 startIdxs부터 입력값의 인덱스까지 뺀 값(입력값이 들어왔음에도 안 빠져있는 경우에는 최대값 : n)에다가 자신의 높이를 곱해 구하면 된다.

 

입력값이 들어왔을 때 다음과 같은 과정을 반복한다.

 

입력값이 더 크거나 같을 경우

원소를 stack에 바로 넣어준다.

 

입력값이 더 작은 경우

오름차순 Monotonic Stack을 재구성해야 한다.

먼저 top에 있는 원소를 빼고, 그 원소에 대한 넓이를 구해준다.

스택이 비게되거나 입력값이 더 커질 때까지 반복한다.

그리고 원소를 stack에 넣어준다.

 

그리고 마지막에 stack에 남아있는 원소들에 대해, 각각 넓이를 구해주면 주어진 조건의 정답을 구할 수 있다.

소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    int answer = 0;
    // idx, value
    stack<pair<intint>> st;
    // 넓이 계산 시 사용
    vector<int> startIdxs(n);
 
    for (int idx = 0; idx < n; ++idx)
    {
        int height = 0;
        cin >> height;
        int width = 0;
        startIdxs[idx] = idx;
 
        // 입력값이 더 작다면, 앞의 요소 꺼내야 함.
        while (!st.empty() && st.top().second >= height)
        {
            int i = st.top().first;
            int h = st.top().second;
            startIdxs[idx] = startIdxs[i];
            st.pop();
            // 꺼낼 때 넓이 계산
            width = h * (idx - startIdxs[i]);
            answer = max(answer, width);
        }
 
        st.push({ idx, height });
    }
 
    // 남아 있는 요소들에 대해서 넓이 재확인
    while (!st.empty())
    {
        int i = st.top().first;
        int h = st.top().second;
        st.pop();
        int width = h * (n - startIdxs[i]);
        answer = max(answer, width);
    }
 
    cout << answer;
 
    return 0;
}
cs
반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준 2108] 통계학 C++  (0) 2023.12.23
[백준 3015] 오아시스 재결합 C++  (2) 2023.12.02
[백준 2564] 경비원 C++  (3) 2023.05.30
[백준 4811] 알약 C++  (0) 2023.05.15
[백준 2302] 극장 좌석 C++  (0) 2023.05.11