leet code : trapping rain water, 백준 : 히스토그램 6549

알고리즘 문제 풀기

leet code : trapping rain water, 백준 : 히스토그램 6549

studying develop 2020. 2. 25. 15:44

내가 전에 면접 문제로 풀어본 문제다 난 히스토그램 문제랑 비슷하게 생각해서 했는데 탈락했다 ㅋㅋ

다시 풀어보자 여러 방법으로 과연 내가 왜 틀렸던 것인가 풀이가 틀린게 아니라면 내가 못알아 듣게 말한게 큰거 같다.

면접에서 일단 첫구현인 내가 생각했던 방법이다.

틀렸따. ㅋㅋ

class Solution {
public:
    int trap(vector<int>& height) {
        int cur;
        int sum=0;
        
        for(int i=0;i<height.size();i++)
        {
            int left = i,right= i;
            
            while(left-1 >=0 && height[left-1] > height[left]){
                left -= 1;
            }
            while(right+1 < height.size() && height[right] < height[right+1]){
                right += 1;
            }
            
            cout << left << " "<< right<< "\n";
            
            int smaller_height = min(height[left],height[right]);
            
            for(int j = left+1;j<right && height[i] < height[left] && height[i] < height[right]; j++){
                cout << sum <<"\n";
                if(smaller_height - height[j] > 0 )
                    sum += (smaller_height - height[j]);
            }
            
            i = right;
            
        }//for
        
        
        return sum;
    }//trap
};

반례

[5,2,1,2,1,5]

결국 양쪽에 엄청 높은게 있으면 우물안에서는 양쪽에서 어느 기둥이 가장 높은것인지 알 수 없었다.

난 히스토그램 문제랑 비슷하다고 생각했다. 근데 그냥 하다 떠오른 생각인데 안된다 생각했는데 이게 더 맞는거 같다. 그냥 세그먼트 트리 이용해서 양쪽에서 가장 높은 기둥 찾으면 되는거 아닌가?

그리고 써보니까 릿코드 문제 좋은거 많은거 같다. 꼭 풀어보자 ㅋㅋ

일단 좀 고쳐보았따.

class Solution {
public:
    int trap(vector<int>& height) {
        int cur;
        int sum=0;
        
        for(int i=0;i<height.size();i++)
        {
            int left = i,right= i;
            
            while(left-1 >=0 && height[left-1] > height[left]){
                left -= 1;
            }
            while(right+1 < height.size() && (height[right] < height[right+1]) ){
                right += 1;
            }
                 
            //이때 왼쪽 기둥이 오른쪽에서 찾은 기둥보다 높으면, 찾은 오른쪽 볼록 기둥 기준 오른쪽에 
            //왼쪽 기둥 보다 높은 기둥이 있는 지 확인해야 한다.
            //세그 먼트 트리 이용?
            
            cout << left << " "<< right<< "\n";
            
            int smaller_height = min(height[left],height[right]);
            
            for(int j = left+1;j<right && height[i] < height[left] && height[i] < height[right]; j++){
                cout << sum <<"\n";
                if(smaller_height - height[j] > 0 )
                    sum += (smaller_height - height[j]);
            }
            
            i = right;
            
        }//for
        
        
        return sum;
    }//trap
};

이 문제는 왜 직관적으로 그냥 풀면 틀리는 걸까 음.... 히스토그램 처럼 왼쪽에 가장 큰 놈을 저장해놓는 다면? 근데 이 풀이를 왜 이렇게 외워서 하는거 같지 자연스럽게 도출해보자...

다른 방법을 생각해 보았다.

기둥 들이 있을때 해당 위치에서 양쪽에 가장 긴 두 벽을 찾아야 한다. 그리고 그중에 더 짧은 벽의 길이를 알면 된다.

일단 가장 긴 두개를 찾고 그 영역을 제외한 (각 끝 기둥은 포함하는) 양쪽 영역에서 다시 가장 긴 길이를 찾으면 분할 정복으로 풀릴거 같다.

근데 같은게 여러개 있으면 제대로 작동 안한다....... 그러면 우선순위를 좀 주어야 하는데 인덱스에 따라서 좀 준다 치면 세그먼트 트리가 두가지 요인 인덱스,높이로 고를 수 있다.... 복잡해짐 다른 쉬운 방법은 없나.

해설 <https://www.google.com/search?q=trapping+rain+water&oq=trapping+rain+water&aqs=chrome..69i57j0l3j69i60j69i65j69i61j69i60.6616j1j7&sourceid=chrome&ie=UTF-8>

보다가 알았는데 일단 기본은 빅 O를 생각하지 말고 풀어보자. 다시 원점에서 ㅋㅋ;; 이전에는 잘못 풀었으니까

낼하장

그냥 지금 해봤는데, 한개 기둥 정하고, 오른쪽으로 가면서 그 기둥보다 크거나 같은걸 찾으면 된다. 그냥 그러면 되는거 아닌가....

그런데 그럼 주어진 예제의 맨 오른쪽을 찾지 못하니까 그런 경우는 그냥 가장 높은걸 기준으로 하면 될듯?

[0,1,0,2,1,0,1,3,2,1,2,1]

컴파일 에러;;

class Solution {
public:
    int trap(vector<int>& height) {
        int cur;
        int sum=0;
        int left,right;
        
        for(left=0;left<height.size();left++)
        {
            //right를 구한다.
            while(height[left] > height[right] && right < height.size()  ){
                right++;
            }
            
            //left - right 사이 면적 계산.
            int min_height = min(height[left],height[right]);
            for(int j=left+1;j<right;j++){
                if( min_height - height[j] >0 )
                sum += min_height - height[j];
            }
            //left = right
            left = right;
            
        }//for
        
        
        return sum;
    }//trap
};

고쳤는데 여전히;

class Solution {
public:
    int trap(vector<int>& height) {
        int cur;
        int sum=0;
        int left,right;
        
        int max_right_ind;
        
        for(left=0;left<height.size();)
        {
            //right를 구한다.
            right = left+1;
            max_right_ind = right;
            while(height[left] > height[right] && right < height.size()  ){
                right++;
                if(height[right] >= height[max_right_ind])
                    max_right_ind = right;
            }
            
            if(right == height.size())
                right = max_right_ind;
            
           // cout << left<<" "<< right<<"\n";
            
            //left - right 사이 면적 계산.
            int min_height = min(height[left],height[right]);
            
            for(int j=left+1;j<right;j++){
                if( min_height - height[j] >0 ){
                    sum += min_height - height[j];
    //                cout << sum<<"\n";
                }
            }
            //left = right
            left = right;
            
        }//for
        
        
        return sum;
    }//trap
};

class Solution {
public:
    int trap(vector<int>& height) {
        int cur;
        int sum=0;
        
        for(int i=0;i<height.size();i++)
        {
            int left = i,right= i;
            
            while(left-1 >=0 && height[left-1] > height[left]){
                left -= 1;
            }
            while(right+1 < height.size() && (height[right] < height[right+1]) ){
                right += 1;
            }
                 
            //이때 왼쪽 기둥이 오른쪽에서 찾은 기둥보다 높으면, 찾은 오른쪽 볼록 기둥 기준 오른쪽에 
            //왼쪽 기둥 보다 높은 기둥이 있는 지 확인해야 한다.
            //세그 먼트 트리 이용?

        //   cout << left << " "<< right<< "\n";

            int taller = max(height[left],height[right]);
            
            int left_max;
            int right_max;
            
            if(height[left] < taller){
                left_max = left;
                
                while(left-1 >=0 && height[left] <= taller){
                   left -= 1;
           //         cout << left<<"\n";
                    if(height[left_max] <= height[left]){
                        left_max = left;
                    }
                }      

                left = left_max;
                    
            }
            else if(height[right] < taller){
                right_max = right;
          //      cout << "rm :"<<right_max<<"\n";
                while(right+1 < height.size() && height[right] <= taller){
                    right += 1;
                    if(height[right_max] <= height[right]){
           //             cout << "r :"<<right<<"\n";
                        right_max = right;
                    }
                }      

                right = right_max;
            }
            
            int smaller_height = min(height[left],height[right]);
            
          //  cout << left << " "<< right<< "\n\n";
          //  cout << smaller_height<<"\n";
            
            for(int j = left+1; j<=right; j++){

             //   cout << j<<"\n";
                if(smaller_height - height[j] > 0 ){
                //    cout << smaller_height - height[j]<<"\n";
                    sum += (smaller_height - height[j]);
                }
            //                    cout << sum <<"\n";
            }
            
            i = right;
            
        }//for
        
        
        return sum;
    }//trap
};

[7,6,7,6,9]

결국 맞았따. 좀 복잡하다. ㅋㅋ

class Solution {
public:
    int trap(vector<int>& height) {
        int cur;
        int sum=0;
        
        for(int i=0;i<height.size();i++)
        {
            int left = i,right= i;
            
            while(left-1 >=0 && height[left-1] > height[left]){
                left -= 1;
            }
            while(right+1 < height.size() && (height[right] < height[right+1]) ){
                right += 1;
            }
                 
            //이때 왼쪽 기둥이 오른쪽에서 찾은 기둥보다 높으면, 찾은 오른쪽 볼록 기둥 기준 오른쪽에 
            //왼쪽 기둥 보다 높은 기둥이 있는 지 확인해야 한다.
            //세그 먼트 트리 이용?

         //  cout <<"1st: "<< left << " "<< right<< "\n";

            int taller = max(height[left],height[right]);
            
            int left_max;
            int right_max;
            
          //  cout << "taller: "<<taller<<"\n";
            
            if(height[left] < taller){
                left_max = left;
                
                while(left-1 >=0 && height[left] < taller){
                   left -= 1;
           //         cout << left<<"\n";
                    if(height[left_max] <= height[left]){
                        left_max = left;
                    }
                }      

                left = left_max;
                    
            }

            else if(height[right] <= taller){
                right_max = right;
           //     cout << "rm :"<<right_max<<"\n";
                while(right+1 < height.size() && height[right] <= taller){
                    right += 1;
                    if(height[right_max] <= height[right]){
               //         cout << "r :"<<right<<"\n";
                        right_max = right;
                    }
                }      

                right = right_max;
            }
            
            int smaller_height = min(height[left],height[right]);
            
          //  cout << left << " "<< right<< "\n\n";
          //  cout << smaller_height<<"\n";
            
            for(int j = left+1; j<=right; j++){

             //   cout << j<<"\n";
                if(smaller_height - height[j] > 0 ){
                //    cout << smaller_height - height[j]<<"\n";
                    sum += (smaller_height - height[j]);
                }
            //                    cout << sum <<"\n";
            }
            
            i = right;
            
        }//for
        
        
        return sum;
    }//trap
};

섭미션이나, 다른 넥스트 챌린지를 보니까 도움이 많이 된다. 일단 이 유형을 다른 사람들은 어떻게 풀었는지 좀 보자. 남의 코드도 걸린 시간 별로 볼 수 있다.

0ms 시간대.....

class Solution {
public:
    int trap(vector<int>& height) {
        
        if(height.size() == 0) return 0;
        
        int len = height.size();
        int max_r[len];
        int curr;
        max_r[len-1] = height[len-1];
        for(int i = len-1; i > 0; i--){
            if(height[i-1] > max_r[i]){
                max_r[i-1] = height[i-1];
            } else {
                max_r[i-1] = max_r[i];
            }
        }
        int max_l = height[0];
        int diff = 0;
        int totalWater = 0;
        for(int i = 1; i < len-1; i++){
            if(height[i] > max_l){
                max_l = height[i];
            }
            
            diff = min(max_r[i], max_l) - height[i];
            if(diff > 0){
                totalWater = totalWater + diff;
            }
        }
        return totalWater;
    }
};

이 방법은 dp에 가까운거 같다. 즉

max_r[i]의 정의가 중요한데

i번째 위치의 오른쪽에 위치한 물이 담기는 기둥이다.

나는 오른쪽,왼쪽에서 가장 큰 벽을 찾는것을 매우 비효율적으로 했다. 어떻게 위 처럼 그냥 좌우에서 쭉 오면서 바로 결정할 수 있음을 알았지?

그런데 약간 비슷한 논리인데 이분 풀이가 훨씬 간결하다. 이 분은 그냥 어차피 가두리 양쪽중 작은 쪽을 기준으로 물이 차니까 아래처럼 한번에 풀 수 있다.

public int trap(int[] A){
    int a=0;
    int b=A.length-1;
    int max=0;
    int leftmax=0;
    int rightmax=0;
    while(a<=b){
        leftmax=Math.max(leftmax,A[a]);
        rightmax=Math.max(rightmax,A[b]);
        if(leftmax<rightmax){
            max+=(leftmax-A[a]);       // leftmax is smaller than rightmax, so the (leftmax-A[a]) water can be stored
            a++;
        }
        else{
            max+=(rightmax-A[b]);
            b--;
        }
    }
    return max;
}

히스토그램

[https://www.acmicpc.net/blog/view/12] 백준 풀이.

이런 말이 있다.

히스토그램에서 모든 막대의 너비는 1이고, 높이는 hi일 때, 가장 넓이가 큰 직사각형을 찾아야 합니다.

모든 막대 x에 대해서, x를 높이로 하면서 만들 수 있는 가장 큰 직사각형을 찾아야 합니다.

이렇게 명확히 하니 일단은 다른 아예 문제다 ㅋㅋ

음 아닌가 다시 생각하니 내가 왜 비슷하다 생각한지 알거 같다. 나도 비슷하게 해석했다. 답을 구하려면 현재 위치에서 만들 수 있는 가장 깊은 골을 만든다 생각한 것이다.!! 하지만 직사각형을 만드는 것과는 조금 다를 수도 있는것이다.

'알고리즘 문제 풀기' 카테고리의 다른 글

투포인터 - 백준:2143번 두 배열의 합 (0)	2020.02.26
백준 1806번 : 부분합(투포인터) (0)	2020.02.26
백준 2517번 : 달리기 (0)	2020.02.25
백준 2580번 스도쿠, 1799번 비숍 (0)	2020.02.24
백준 2098번: 외판원 순회, 9251번 lcs (0)	2020.02.14

현재글leet code : trapping rain water, 백준 : 히스토그램 6549

swift, python, java, 아이폰 앱 개발, 안드로이드 앱 개발, 서버 공부, 머신러닝 공부, 그래픽스 공부 등등 기록입니다.

IOS, 파이썬, 알고리즘, 면접 대비, leetcode, Django, URLSessionTask, 백준, 스프링부트, 프로그래머스, 안드로이드, node.js, SWIFT, 스위프트, 스택, 함수형 프로그래밍, present, watchConnectivity, 릿코드, application.properties,

Today :
Yesterday :

개인적으로 공부한 내용을 정리중입니다.