LeetCode 42. Trapping Rain Water

문제

https://leetcode.com/problems/trapping-rain-water/

걸린 시간

-

풀이

C++

typedef pair<int, int> pii;

class Solution {
public:
    int trap(vector<int>& h) {
        int n = h.size();
        vector<int> height(n+2, 0);
        for(int i = 1; i <= n; i++){
            height[i] = h[i-1];
        }
        vector<pii> hill; // height, idx
        for(int i = 1; i <= n; i++){
            if(height[i-1] <= height[i] && height[i] >= height[i+1]){
                hill.push_back({height[i], i});
            }
        }
        vector<pii> bound;
        for(int i = 0; i < hill.size(); i++){
            int l = 0, r = 0;
            int c = hill[i].first;
            for(int j = 0; j < i; j++){
                l = max(l, hill[j].first);
            }
            for(int j = i+1; j < hill.size(); j++){
                r = max(r, hill[j].first);
            }
            if(!(c < l && c < r)){
                bound.push_back(hill[i]);
            }
        }
        int ans = 0;
        int size = bound.size();
        for(int i = 0; i < size-1; i++){
            int l = bound[i].second;
            int r = bound[i+1].second;
            int w = r-l-1;
            int h = min(bound[i].first, bound[i+1].first);
            int b = 0;
            for(int j = l+1; j < r; j++){
                b += min(h, height[j]);
            }
            ans += w*h-b;
        }
        return ans;
    }
};

간단히 풀이를 설명하면

1. 언덕이 되는 블록을 모두 구한다.
2. 양 옆의 다른 언덕에 의해 물에 잠기는 언덕을 제거한다.
3. 잠기는 물의 부피를 계산한다.

n 이 10⁴밖에 되지 않아서 가능한 풀이였던 것 같다. 이 밖에 투포인터와 스택을 이용한 풀이가 있다고 한다.

vector 의 size 메소드는 unsigned integer 자료형을 반환하기 때문에 언더플로에 유의해야한다.

릿코드가 실패한 테스트케이스를 보여주지 않았다면 더 많이 삽질했을 문제. 꼼꼼하지 못해서 제출을 여러번이나 했다.