08. Trapping Rain Water

🎯 leetcode - 42. Trapping Rain Water

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 8번 문제

📌 날짜

2020.01.21

📌 시도 횟수

4try / FAIL

📌 실패 코드

class Solution:
    def trap(self, height: List[int]) -> int:
        point = 0
        first_peek, second_peek = 0, 0
        count = 0
        i = 1
        while i < len(height):
            if self.descending(height[i - 1], height[i]):
                point = height[i]
                i += 1
            else:
                while i < len(height) and not self.descending(height[i - 1], height[i]):
                    second_peek = i
                    i += 1
                if height[second_peek] > height[first_peek]:
                    for j in range(first_peek + 1, second_peek):
                        count += height[first_peek] - height[j]
                else:
                    for j in range(first_peek + 1, second_peek):
                        count += height[second_peek] - height[j]
                if second_peek > first_peek:
                    first_peek = second_peek
        return count

    def descending(self, p1, p2):
        if p1 > p2:
            return True
        else:
            return False

• 문제 이해를 제대로 하지 못해서 일부 test case에서만 통과함을 확인할 수 있다.
• 

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 문제를 제대로 이해하지 못했다...
- 변곡점(꺾이는 부분) 찾기까지는 가능했는데,
그 이후 변곡점을 찾아서 쌓일 수 있는 물을 계산하는 것을 구현하지 못했다.
- 아직 이런 문제를 만나면 다양한 방법들이 떠오르지 않는다.. 투 포인터도 어떻게 사용해야 할 지 감이 안온다ㅠㅠ

---

😉 다른 풀이

📌 하나. 투 포인터 이용하기

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        left, right = 0, len(height) - 1
        volume = 0
        left_max, right_max = height[left], height[right]
        while left < right:
            left_max, right_max = max(left_max, height[left]), 
            			  max(right_max, height[right])
            if left_max < right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1

        return volume

💡 새롭게 알게 된 점

- 투 포인터로 풀 수 있음을 알게 되었다..
- 이 문제는 계속 많이 풀어봐야 겠다...