[BOJ] 백준 6198번 옥상 정원 꾸미기 - C++ 코드, 해설, 풀이

 

백준 6198번 옥상 정원 꾸미기 문제 풀이입니다.

6198번: 옥상 정원 꾸미기 (acmicpc.net)

6198번: 옥상 정원 꾸미기

 

 

 

2006 USACO Silver 문제입니다. 개인적으로 문제 푸는데 이걸 스택으로 푼다는 걸 떠올리는데 오래걸렸던 것 같습니다.

 

 

문제 요약 및 분석

왼쪽에서 오른쪽으로 각 빌딩에 대해서 크거나 같지 않은 빌딩의 개수를 구하는 문제가 되겠습니다.

일단 입력을 보았을 때 N = 8 x 10^4 입니다. N^2으로 풀면 시간 초과가 날 것 같고 N이나 NlogN 알고리즘을 떠올리며 접근해보았습니다.

 

풀이 방법

i = 2부터 자기보다 큰 빌딩(오른쪽에 위치한)이 몇개인지 안다면 정답을 구할 수 있습니다.

빌딩 높이	10	3	7	4	12	2
빌딩 번호 = i	1	2	3	4	5	6
i=2	1
i=3	1
i=4	1		1
i=5
i=6					1

위 표와 같이 각 페이즈(i번째)별로 더해질 수 있는 빌딩을 생각해볼 수 있는데 이 형태를 stack 자료구조에 적용해보면

i번째에서 stack에 자기보다 큰 빌딩만 남아있다면 그때의 stack.size()를 누적해서 더해갈 수 있겠다는 생각이 들었고, 모든 빌딩을 push, pop이 최대 한번씩 일어날 수 있기 때문에 O(2n)으로 linear한 시간복잡도로 문제를 해결할 수 있습니다.

 

정답 중 핵심코드

void solve() {
    string s, strn;
    stack<int> stk;
 
    cin >> n;
    vector<int> v(n);
    for (i = 0; i < n; i++) {
        cin >> v[i];
    }
    stk.push(v[0]);
 
    for (i = 1; i < n; i++) {
        while (!stk.empty()) {
            if (v[i] >= stk.top()) {
                stk.pop();
            } else {
                break;
            }
        }
        ans += stk.size();
        stk.push(v[i]);
    }
    cout << ans << endl;
}
 

12번 line을 보면 i = 1 ~ n-1 까지 for문을 돌면서

해당 빌딩 차례 때 그 빌딩보다 작은 빌딩을 하나씩 top에서 확인하면서 pop하게 됩니다.(큰 빌딩이 나올 때 까지)

그리고 20 line에서 살아남은(해 빌딩보다 더 큰) 빌딩을 ans에 누적 합계하여 계산해줍니다.

 

나중에 난이도 기여하려고 찾아보니 '모노톤 스택'의 대표적인 문제라고 합니다. '모노톤 스택'에 대해서도 공부하고 블로그에서 한번 다뤄보겠습니다.