42. Trapping Rain Water

• 문제를 두 부분으로 나누어 풀어야 한다는 점을 깨닫는데 오래 걸렸다.

• 조건 및 예시를 관찰하면 알 수 있는 사항은 아래와 같다.
• 물이 고여있는 부분은 이전에 출연했던 높이 중 가장 큰값과 같거나 클 경우 생긴다.
• 문제는 가장 높이가 높은 막대를 기준으로 오른쪽에서는 높이가 낮은 곳에서도 물이 고이는 부분이 생긴다.

• 따라서 문제는 높이가 가장 높은 막대를 기준으로 왼쪽, 오른쪽으로 나누어 접근한다.
• 먼저 왼쪽에서부터 높이가 이전과 비교하여 같거나 높은 막대가 등장할 때 마다 기록한다.
• 그 다음 가장 높은 막대를 기준으로 오른쪽 부분은 역방향으로 탐색하며 높이가 이전과 비교하여 같거나 높은 막대가 등장할 때 마다 기록한다.

• 이렇게 기록된 막대와 막대 사이의 웅덩이에 고인 물의 양을 기록한다.

class Solution {
public:
    int trap(vector<int>& height) {
        vector<pair<int, int>> leftPivots;
        for (int i = 0; i < height.size(); ++i) {
            auto h = height[i];
            auto topHeight = (!leftPivots.empty())
                ? leftPivots.back().first : 0;
            if (h > 0 && h >= topHeight)
                leftPivots.emplace_back(h, i);
        }
        if (leftPivots.empty()) return 0;

        auto lastPivot = leftPivots.back();
        vector<pair<int, int>> rightPivots;
        for (int i = height.size() - 1; i > lastPivot.second; --i) {
            auto h = height[i];
            auto topHeight = (!rightPivots.empty())
                ? rightPivots.back().first : 0;
            if (h > 0 && h >= topHeight)
                rightPivots.emplace_back(h, i);
        }
        int result = 0;
        int prevHeight = 0, currHeight = 0;
        int start = 0, end = 0;
        for (int i = 0; i < leftPivots.size(); ++i) {
            tie(currHeight, end) = leftPivots[i];
            for (int j = start + 1; j < end; ++j) {
                result += prevHeight - height[j];
            }
            start = end;
            prevHeight = currHeight;
        }
        for (int i = rightPivots.size() - 1; i >= 0; --i) {
            tie(currHeight, end) = rightPivots[i];
            for (int j = start + 1; j < end; ++j) {
                result += currHeight - height[j];
            }
            start = end;
        }
        return result;
    }
};

• 두번째 해답은 기록하지 않고 바로바로 계산하는 방법이다.
• 이전 높이보다 높은 막대가 등장할 때 마다 계산을 수행한다.

class Solution {
public:
    int trap(vector<int>& height) {
        int result = 0;
        int end = 0, prevHeight = 0, subSum = 0;
        for (int i = 0; i < height.size(); ++i) {
            auto h = height[i];
            if (h > 0 && h >= prevHeight) {
                if (prevHeight > 0) result += subSum;
                subSum = 0;
                prevHeight = h;
                end = i;
            } else {
                subSum += prevHeight - h;
            }
        }
        if (prevHeight == 0) return 0;
        prevHeight = 0;
        for (int i = height.size() - 1; i >= end; --i) {
            auto h = height[i];
            if (h > 0 && h >= prevHeight) {
                if (prevHeight > 0) result += subSum;
                subSum = 0;
                prevHeight = h;
            } else {
                subSum += prevHeight - h;
            }
        }
        return result;
    }
};