[LeetCode 풀이/python] 42. Trapping Rain Water (hard)

문제 설명: 0 이상의 정수 n 개로 표현되며 각 bar 의 폭이 1인 elevatation map height 가 주어졌을 때, 비가 내린 후 얼마나 많은 양의 빗물을 가둘(trap) 수 있는지 계산하시오.

 

(Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.)

 

예시 1)

입력: height = [0,1,0,2,1,0,1,3,2,1,2,1]  -->  출력: 6

설명: 검게 칠해진 부분이 elevation map 을 나타내며, 파랗게 칠해진 부분이 가둬진 빗물을 나타냄

 

예시 2)

입력: height = [4,2,0,3,2,5]  -->  출력: 9

 

제한 조건:

• n == height.length
• 0 <= n <= 3 * 10^4
• 0 <= height[i] <= 10^5

------ * ------ * ------ * ------

 

[풀이 1안] - not a solution

• 접근법
  • 배열 height 의 각 높이 별로 trap 가능한 인덱스 범위를 체크  -->  각 높이 값을 dictionary 의 key 로 & 해당하는 인덱스를 value list 로 저장 
  • 배열을 차례로 탐색하며, 처음 해당 높이가 initiate 된 이후 해당 높이보다 크거나 같은 높이가 나오면 trap 가능하므로 해당 범위를 체크

 

• 코드 구현

def trap(height: List[int]) -> int:
    start_idx = dict()
    cnt = 0
    for i, h in enumerate(height):
        if h == 0: continue

        if h not in start_idx:
            for l in range(1, h+1):
                if l not in start_idx:
                    start_idx[l] = i
                    
        for s in start_idx:
            if s <= h:
                cnt += max(i-start_idx[s]-1, 0)
                start_idx[s] = i

    return cnt

 

• 결과
  • 예시 케이스는 통과하나 Submit 시 Time Exceed Error 발생...
  • 배열의 길이 n & 높이 height 에 대해 각각 linear 하게 탐색하는 셈이므로 비효율적일 수 밖에...
  • m = max(height) 의 최대 값이 n 의 최대 값보다도 클 수 있으므로, start_idx 의 키 값을 순회하는 과정에서 계산량이 매우 커짐  -->  결과적으로 O(n^2) 보다 못한 O(n*m) 인 것 흑흑 ㅜㅜ
  • 관련 토픽으로 Two Pointers 와 Stack 이 나오는데 어떻게 접근해야할 지 모르겠으므로 Discussion 을 참고해본다...

 

[풀이 2안]

• 접근법
  • Two Pointers 접근법을 이용한 풀이를 참고함
  • 배열의 양 끝에서부터 탐색을 진행하며 각 인덱스에서 trap 가능한 물의 양을 더해줌
  • 최대 높이가 물을 가두는 벽과 같은 역할을 하므로, 양 끝에서부터 왼 / 오 각각의 최대 높이를 저장 & 업데이트
  • 왼->오 진행 기준으로 생각하면, 왼쪽 최대 높이에서 해당 인덱스의 height 값을 뺀 만큼을 trap 가능
  • 기본적으로 l_max 보다 r_max 가 큰 상황에서 cnt 를 더해주게 되어 있으므로, 해당 인덱스에서 물이 trap 되는 것이 보장됨(*)

 

• 코드 구현

def trap(height):
    cnt = 0
    if len(height) < 3: return cnt
        
    l, r = 0, len(height)-1
    l_max, r_max = height[l], height[r]
        
    while l <= r:
        l_max, r_max = max(l_max, height[l]), max(r_max, height[r])
        if l_max <= r_max:
            cnt += (l_max - height[l])
            l += 1
        else:
            cnt += (r_max - height[r])
            r -= 1 

    return cnt

 

• 결과
  • O(n) 의 복잡도로 해결 가능...!
  • l_max <= r_max 진행 조건을 이해하는 데에 시간이 좀 걸렸다 ㅜ_ㅜ

 

[풀이 3안]

• 접근법
  • 다른 풀이들을 리뷰하다가 또다른 신기한 풀이를 발견... 2번 풀이랑 비슷한 맥락인 듯함
  • 배열의 왼 / 오 양 끝에서 탐색을 진행하며 최대 높이를 업데이트 하되, 왼 -> 오 탐색 기준 최대 값과 오 -> 왼 탐색 기준 최대 값을 별도의 배열로 저장
  • 왼 / 오 최대 높이 중 더 작은 수만큼이 trap 될 수 있으므로, 각 인덱스에 대해 min(왼 / 오 높이) 에서 해당 인덱스의 높이를 뺀 값이 trap 가능한 물의 양과 같음

 

• 코드 구현

def trap(height):
    cnt = 0
    if len(height) < 3: return cnt
        
    l_max, r_max = height[0], height[len(height)-1]
    l_maxes, r_maxes = [l_max], [r_max]
        
    for l in height[1:]:
        l_max = max(l_max, l)
        l_maxes.append(l_max)
        
    for r in reversed(height[:-1]):
        r_max = max(r_max, r)
        r_maxes.append(r_max)
        
    for i in range(len(height)):
        cnt += (min(l_maxes[i], r_maxes[-(i+1)])-height[i])
            
    return cnt

 

• 결과
  • 시간 복잡도는 2번 풀이와 동일하게 O(n) 이지만, for loop 을 3번 도는 점 & 왼 / 오 최대 높이를 별도 배열로 저장한다는 점에서 시간 / 공간 복잡도 모두 증가하는 것으로 확인됨