[Codility] StoneWall

가능한 적은 수의 돌을 써서 주어진 배열 H에 맞게 돌벽을 짓는 문제.

낮은 벽에 사용되는 돌이 큰 돌의 받침에도 쓰이도록 했을 때, 항상 최소 개수만이 요구된다는 점을 이용하면 된다.

h 크기의 벽 뒤에 더 큰 벽을 쌓고 다시 h 크기의 벽을 쌓아야 한다면 새로운 돌이 필요가 없다. 스택을 이용하면 큰 벽을 쌓고 다시 낮은 벽이 요구될 때 큰 벽 이전의 벽 크기와 비교할 수 있다.

https://app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/

cpp code

#include <stack>

int solution(vector<int> &H) {
    int ans = 0;
    stack<int> S;
    int cur_h = 0;
    for (int i = 0; i < H.size(); i++) {
        while (H[i] < cur_h) {
            cur_h = S.top();
            S.pop();
        }
        if (H[i] > cur_h) {
            S.push(cur_h);
            cur_h = H[i];
            ans++;
        }
    }
    return ans;
}