[LeetCode 42] Trapping Rain Water

• Think

  혼자 풀기 실패

  풀이 설명을 읽는데 이해가 안됨

  리트 코드 solution탭을 살펴봤는데 아래 그림 보고 설명 바로 이해함!!
  

  

• Solution

  1. 투 포인터 사용

      class Solution(object):
          def trap(self, height):
              """
              :type height: List[int]
              :rtype: int
              """
                      #빈 인풋값이 들어왔을 경우를 처리
                      if not height :
                              print(0)
     
              left = 0
              right = len(height) - 1 #포인터 0부터 시작
              left_max, right_max = height[left], height[right]
              volume = 0
     
              while left < right : #서로 만나기 전까지 실행
                  #왼, 오 최댓값을 현재값과 비교해 갱신
                  left_max = max(left_max, height[left])
                  right_max = max(right_max, height[right])
     
                  #더 작은 값이 큰 값쪽으로 한 칸 이동, 이동하면서 볼륨(빗물) 계산해 더함
                  if left_max <= right_max :
                      #만약 위에서 갱신이 되어서(현재값이 최대 높이 막대임) 두 값이 동일하다면 0만 더해짐
                      #만약 위에서 갱신이 되지 않았다면(현재값이 최대 높이 막대보다 낮음) 양의 값인 빗물양이 더해짐
                      volume += left_max - height[left]
                      left += 1
                  else :
                      #동일
                      volume += right_max - height[right]
                      right -= 1
     
              return volume

     와 진짜 알고리즘 공부하는 느낌 남..

  2. 스택 사용

     !! 이 풀이도 이후에 꼭 다시 풀어보기

• Get

  • if not A : A가 0이나 빈 문자열 또는 None이면 True를 반환한다. A가 없는가(None)? 라고 생각.
    • 빈 값 등 여러가지 input들이 테스트케이스로 들어올 경우를 고려하여 처리하기
  • 투 포인터 풀이법