[Golang][Algo] Python으로 코딩하고 Go로 한번 더 풀기 -2- Trapping Rain Water

• 파이썬 알고리즘 인터뷰 책을 기반으로 풉니다.
• 파이썬 코드를 기반으로 Go언어로 한번 더 풉니다.
• LeetCode - trapping rain water

Pseudo code

1. 각 인덱스마다 높이를 담는 Stack 생성, 물이 찬 용량 변수 생성
2. 전체 배열 크기만큼 Loop
  2-1. 변곡점을 만나면
    2-1-1. 스택에서 꺼낸다 (Pop)
    2-1-2. 만약 Stack이 비어있으면, 한쪽이 없는 버킷형태 (즉,상향선 혹은 하향선이 하나만 있는 모양이다.) -> 루프 탈출
    2-1-3. 이전과의 차이만큼 물 높이 처리하고 물 찬 용량에 더한다.
  2-2. 변곡점이 아니면 Stack에 인덱스값을 쌓는다.
3. 물이 찬 용량 return

Code

package main

import (
    "fmt"
    "math"
)

type Stack struct {
    nums  []int
    count int
}

func NewStack() *Stack {
    return &Stack{}
}

func (s *Stack) Push(n int) {
    s.nums = append(s.nums, n) // 맨 위에 추가
    s.count++
}

// 스택이 Pop되는 과정은 다음과 같다.
// [1 2 3]
// 3
// [1 2]
// 2
// [1]
// 1
// []
// 0
func (s *Stack) Pop() int {
    if s.count == 0 {
        return 0
    }
    s.count--
    result := s.nums[s.count] // 슬라이스 재배열전에 return값 저장해두고

    if s.count != 0 { // 슬라이스 요소의 갯수가 0이 아닐때
        s.nums = append(s.nums[:s.count], []int{}...) // 슬라이스 마지막 요소 삭제
    } else { // 요소의 갯수가 0일때
        s.nums = nil     // 슬라이스 할당 해제
        s.nums = []int{} // 빈 슬라이스로 재할당
    }
    return result
}

func trap(height []int) int {
    stack := NewStack()
    volume := 0

    for i := 0; i < len(height); i++ {
        // 변곡점일 경우
        for stack.count != 0 && height[i] > height[stack.nums[stack.count-1]] {
            top := stack.Pop()

            // 한쪽이 뚫린 양동이 (즉, 한쪽 상향선만 존재)
            if stack.count == 0 {
                break
            }

            distance := i - stack.nums[stack.count-1] - 1 // distance는 빗물이 담기는 버킷 가로의 길이
            // math.Min은 float64 타입만 비교가능해서 type conversion
            waters := math.Min(float64(height[i]), float64(height[stack.nums[stack.count-1]])) - float64(height[top]) // waters는 물이 차는 버킷의 세로 길이

            volume += distance * int(waters)
        }
        // 변곡점이 아닐경우
        stack.Push(i)
    }

    return volume
}

func main() {
    // height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1} // 6
    height := []int{4, 2, 0, 3, 2, 5} // 9

    result := trap(height)
    fmt.Println(result)

}