LeetCode 42. Trapping Rain Water

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

Trapping Rain Water - LeetCode

 

문제 요약

배열과 배열의 값이 주어졌을때, 배열의 값은 높이를 의미합니다.

위 그림과 같이 빗물이 고일 수 있는 면적을 구하세요.

 

핵심 포인트

 

크게 두 가지 유형으로 빗물의 면적을 구할 수 있습니다.

 

(1) 시작지점의 기둥보다 높은 기둥이 존재 한다

(2) 시작지점의 기둥보다 높은 기둥이 존재 하지 않는다

 

(1)번의 경우 쉽게 면적을 구할 수 있으며, (2)번의 경우 저장된 값 중 시작지점을 제외하고 그 다음으로 높은 기둥을 구해야합니다.

 

 

문제 풀이

 

먼저 전체 코드를 훑어본 다음, 크게 한 단락 씩 코드를 설명하겠습니다.

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, now = 0, pos = 0, next=0; // 1
        for(int i=0; i<height.size(); i++){
            if(height[i]==0) continue;
            stack<int> s;
            s.push(height[i]);
            now = height[i]; 
            for(int j=i+1; j<height.size(); j++){ // 2
                s.push(height[j]);
                next = j;
                if(height[j]>=now) break;
            }
            if(now>s.top()) now = s.top(); // 3
            s.pop();
            while(!s.empty()){
                pos = s.top();
                s.pop();
                if(pos>now) now = pos;
                if(now-pos>0) ans+=now-pos;
            }
            if(next!=height.size()-1) i=next-1; // 4
            else break;
        }
        return ans;
    }
};

 

1. 필요한 변수들을 선언하고 height의 길이만큼 for문을 진행합니다.

        int ans = 0, now = 0, pos = 0, next=0; // 1
        for(int i=0; i<height.size(); i++){
            if(height[i]==0) continue; // 2
            stack<int> s; // 3
            s.push(height[i]); // 4
            now = height[i];  // 5

(1) ans는 정답, now는 시작 지점의 기둥입니다. 나머지 변수는 진행하면서 언급됩니다.

(2) 만약 현재 시작지점 높이가 0이라면 continue를 합니다.

(3) int형 스택을 선언합니다.

(4) 스택에 현재 시작지점의 높이를 저장합니다.

(5) now 변수에 시작지점의 기둥 높이를 저장합니다.

 

2. 다음은 for문안의 또 다른 for문 입니다.

            for(int j=i+1; j<height.size(); j++){ // 1
                s.push(height[j]); // 2
                next = j; // 3
                if(height[j]>=now) break; // 4
            }

(1) 마찬가지로 height의 길이까지 for문을 진행합니다.

(2) 스택에 현재 위치의 높이를 저장합니다.

(3) next에 현재 위치를 저장합니다. next는 다음 시작 지점(=i)을 뜻합니다.

(4) 만약 현재 위치의 높이가 now(시작지점)보다 높다면 break합니다.

 

3. 다음은 while문입니다.

            while(!s.empty()){ // 1
                pos = s.top(); // 2
                s.pop();
                if(pos>now) now = pos; // 3
                if(now-pos>0) ans+=now-pos; // 4
            }

(1) 스택이 빌 때까지 while문을 진행합니다.

(2) 현재 스택의 맨 윗값을 pos에 저장하고 pop합니다.

(3) 만약 pos가 시작지점의 높이값보다 크다면, now에 pos를 저장합니다. 

이 (3)번 문항이 해당되는 경우는 다음 그림과 같습니다.

height배열이 다 끝나가도록 시작지점(맨 왼쪽)의 기둥보다 높은 기둥이 없으므로, 시작지점보다 작지만 빗물을 고이게 할 수 있는 높은 기둥을 저장해야 합니다.

(4) now-pos의 값이 0보다 클 경우, 빗물이 고이는 지역입니다. 해당 면적을 정답에 더해줍니다.

 

4. 다음은 새로이 시작지점을 갱신하는 부분입니다.

            if(next!=height.size()-1) i=next-1;
            else break;

만약 next가 height.size()-1일 경우, 이미 모든 높이를 훑어봤음을 뜻합니다. 이럴 경우에는 break를 합니다.

반대의 경우 이전에 저장했던 next변수의 -1을 새로운 시작지점(=i)으로 저장합니다.

 

5. 정답을 반환합니다.