swift 리트코드 문제풀이 - leetcode 42 빗물 트래핑

swift 리트코드 문제풀이 - leetcode 42 빗물 트래핑

leetcode 42. Trapping Rain Water

 

문제

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

 

 

처음 문제를 보고 이해하는데 시간이 좀 오래 걸렸다. 

일단 주어진 파라미터는 벽 높이가 담긴 배열 하나 이다.

 

[0,1,0,2,1,0,1,3,2,1,2,1] 이 배열에서 하나하나의 숫자는 벽의 높이라는것을 알아두자.

 

그럼 조건을 한번 생각보자.

 

조건1. 벽과 벽사이에 빗물이 찰 수 있는 공간이 있어야 될것 같다. 여기서 중요한건 벽과 벽사이!!

그림에서 보면 첫번째 공간에도 빗물이 차야될것 같지만 그렇지 않다. 왜냐면 오른쪽 벽(index1) 만 존재 하기 때문이다. 

index 1번과 index 3 번째 벽의높이를 보면 각각 1과 2이다. 그래서 index 2번에 빗물이 모일 수 있다.

 

조건2는 빗물이 모일 수 있는 최소 벽의 개수를 생각해 볼 수 있다. 아래 그림처럼 빗물이 1 이라도 모이기 위해서는 최소 3개의 높이 정보가 필요 하다. 여기서 높이 막대기가 두개인데? 라고 생각하면 안된다. 가운데 2번도 높이 막대기이며 높이가 0인 막대기일 뿐이다. 그러니깐 높이 정보가 3개 이하면 빗물의 양은 0이라고 할 수 있다.

조건3은 최소 3개의 높이 정보는 있는데 아래와 같이 가운데 높이가 양쪽 높이 보다 클때이다. 이때는 빗물이 저장될 수 없다. 첫번째 조건처럼 빗물은 두개의 벽 사이에만 저장 될 수 있는데 아래 그림은 벽이 하나 밖에 없기 때문에 빗물의 양이 0이 된다.

그럼 로직을 한번 생각해보자. [0,1,0,2,1,0,1,3,2,1,2,1] 높이 배열이 주어졌다고 가정하고. 아...  설명할려니깐 막막..

 

[1]먼저 기준이 되는 높이를 정해야 한다.

[2]기준 높이는 0 이상이어야 되고, 기준 높이 바로 다음 높이는 기준 높이 보다 크면 안된다.

[3]이 기준 높이를 기준으로 자신과 같거나 자신 보다 높은 숫자(높이)가 나올때까지 찾는다.

 

내가 봐도 어렵다..와..

 

일단 [1]은 첫번째 벽을 찾는 작업이다. 첫번째 벽과 두번째 벽사이에만 빗물이 저장될 수 있으므로!

[2]는 첫번째 벽의 조건인데, 당연히 첫번째 벽의 높이는 0이 될 수 없다. 그리고 첫번째 벽 바로 다음 벽의 높이가 첫번째 벽 높이 보다 높으면 안된다. 왜냐면 물이 고여야 하니깐. 첫번째벽 다음벽은 무조건 첫번째 벽보다 낮아야 된다. 같아도 안된다.!  여기까지 이해가 갔을것 같다...

[3]은 두번째 벽을 찾는 작업이다. 두번째 벽의 조건은 어떻게 될까? 당연히 빗물이 고일려면 첫번째 벽과 높이가 같거나 첫번째 벽보다 높아야 된다. 헥헥..

 

자 그럼 첫번째 벽부터 두번째 벽까지 구했다고 치자. 위의 배열을 가지고 첫번째 벽과 두번째 벽 사이의 배열을 구해보면

[0,1,0,2,1,0,1,3,2,1,2,1] 를 구할 수 있다.

 

첫번째 0은 조건에서 탈락되므로, 1, 0, 2 가 나온다. 첫번째 벽의 높이는 1, 두번째(마지막) 벽의 높이는 2. 좋다. 그럼 여기서 물의 높이는?

첫번째 벽의 높이에서 마지막 벽의 높이 전까지의 벽의 높이를 하나씩 빼주면된다. 말이어렵다. .. 

예를 들면 첫번째 벽의 높이 1이다. 그다음 벽의 높이는 0이다. 즉 이 양벽사이 물의 크기는 1 - 0 = 1이다. 

그다음은 두번째 벽이므로 계산이 끝난다.

 

한번더 해보자.

 

그럼 위의 작업이 끝나면 그 다음 작업은 뭐가 될까? 동일하게 첫번째 벽과 두번째(마지막)벽을 구하는 작업이다.

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

 

위에서 두번째 벽이 이번에는 첫번째 벽이 된다. 높이는 2이다. 그럼이 높이보다 같거나 큰 숫자를 찾을때까지 반복하다가 3을 찾고 멈춘다.

2,1,0,1,3에서 2는 첫번째 벽의 높이다. 마지막 3은 마지막 벽의 높이다. 그럼 2에서 그 다음 숫자들을 하나씩 빼줘보자.

2-1 = 1

2-0 = 2

2-1 = 1

그럼 4가 나온다. 이 양쪽 벽에서는 4만큼의 물을 담을 수 있다.

 

이어서 계속 해보자. [3,2,1,2,1] 남은 배열이다. 첫번째 벽은 3이 되고 마지막벽은?

배열의 끝까지 가도 3이랑 같거나 큰 수는 없다. 

그런데 문제는 벽의 높이 개수가 2개 이상이다. 3과 같거나 큰 높이의 벽은 없지만 왠지 저 배열을 거꾸로 해서 계산해보면 물을 담을 수 있는 공간이 나올 것 같다.

 

위의 빨간색 표시는 배열을 거꾸로 돌려서 다시 계산 하는 조건임.

 

[3,2,1,2,1] 을 거꾸로 해서 다시 재배열해보면 [1,2,1,2,3] 이되고 첫번째 벽과 마지막 벽을 찾아보면

[1,2,1,2,3] 이 된다. 첫번째 벽의 높이는 2이고, 마지막 벽의 높이는 2이다. 그럼 첫번째 벽의 높이 2 에서 그 다음 높이를 빼면

2-1 = 1 이 물의 양이 된다.

 

그리고 그 다음 남은 배열의 숫자가 2개 [2,3] 밖에 없으므로 물을 저장할 수 있는 공간이 없다. 즉 물의 양은 0이된다.

 

위에서 계산한 물의 양을 더해보면 1+4+1 = 6 총 6이 물의 양이 됨을 알 수 있다.

 

아래는 위의 조건들과 시나리오를 토대로 짠 코드임.. 

 

최대한 직관적으로 구현할려고 했다...

 

소스코드 설명은 주석으로 달았는데 충분한지 모르겠네..

 

그럼 20000...

 

var trapHeight = [0,1,0,2,1,0,1,3,2,1,2,1]     //6
//var trapHeight = [4,2,0,3,2,5]                  //9
//var trapHeight = [4,2,3]                            //1
//var trapHeight = [0]                            //0
//var trapHeight = [0,2,0]                            //0
//var trapHeight = [6,4,2,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,3] //83
//var trapHeight = [0,1,0,2,1,0,1,3,2,1,2,1]                              //6
//var trapHeight = [0,1,1,1,1,1,2,1]
//var trapHeight = [4,2,3]
func trap(_ height: [Int]) -> Int {
   
    var sum = 0
    var targetIndex = 0
    var compareIndex = 0
    let length = height.count
    
    //첫번째 벽이 있으면 1, 없으면 0
    var targetNumfind = 0
    
    ///벽은 최소 3개여야 함. 그래야 물의 높이를 계산 할 수 있음
    if height.count < 3 {
        return 0
    }
    
    /// 벽이 3개일때 중간의 벽 높이 값이 양쪽 값 보다 같거나 클 수 없음
    if height.count == 3 {
        if( height[0] <= height[1]) || (height[1] >= height[2]){
            return 0
        }
    }
    
    while(targetIndex <= length - 2){
        let targetNum = height[targetIndex]
        let nextNum = height[targetIndex+1]
        
        //비교숫자의 index는 기준 숫자 index+1
        compareIndex = targetIndex+1
                
        if targetNum == 0 || targetNum <= nextNum {
            print("타겟넘버가(기준벽) 0이거나 타겟 넘버 뒤의 숫자와 같거나 작다")
        }else{
            
            targetNumfind = 1
            
            while compareIndex <= length - 1 {
                
                let compareNum = height[compareIndex]
                
                print("tIndex:\(targetIndex) ,targetNum: \(targetNum) , cIndex: \(compareIndex) compareNum : \(compareNum)")
                
                if targetNum <= compareNum{
                        targetNumfind = 0
                        
                        print("자신보다 같거나 큰 숫자 찾음 compareIndex : \(compareIndex) -> targetIndex")
                        print("**snapShot targetIndex:\(targetIndex) , compareIndex : \(compareIndex)")
                        let newArray = Array(height[targetIndex...compareIndex])
                        let newArrayLength = newArray.count
                        var newIndex = 1
                        let newTargetNum = newArray[0]
                        var _sum = 0
                        print("**배열범위 : \(newArray)")
                        // 빗물양 누적하기
                        while newIndex < newArrayLength-1{
                            let result = newTargetNum - newArray[newIndex]
                            _sum += result
                            newIndex+=1
                        }
                        print("**중간합계 : \(_sum)")
                        // 빗물양 누적하기
                        sum += _sum
                        targetIndex = compareIndex - 1
                    break
                
                }else{
                    print("못찾음!!!!")
                    print("targetNumFind : \(targetNumfind)")
                    if(targetNumfind == 1 && (compareIndex - targetIndex > 1) && compareIndex == length - 1){
                        print("뒤집어서 다시 빗물양 계산")
                        sum += trap(height[targetIndex...compareIndex].reversed())
                        return sum
                    }
                }
                
                compareIndex+=1
            }//while in - end
        }
        targetIndex+=1
    
    }//while out - end

    return sum
}

print(">>>> trap :\( trap(trapHeight) )") //6

 

결과

 

 

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