[Algorithm] Brute Force 사용하여 Trapping Rain 구현

 

[ Brute Force 알고리즘을 사용하여 trapping rain 빗물의 양을 구하기 ]

 

 

건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴해주는

trapping_rain 함수를 작성.

 

ex) 파라미터 buildings로 [0,1,0,2,1,0,1,3,1,2,1] 을 받았을 때, 총 6의 빗물이 채워진다.

 

 

문제를 접했을 때 풀이 방법이 떠오르지 않고 힌트를 봐도 이해가 한번에 되지 않았기에

가장 기본적인 알고리즘이지만 다시금 정리해 본다.

 

---

Brute Force 란?

: 무차별 대입 알고리즘

 

장점 ▷ 직관적이고 명확하다. 확실하게 답을 찾을 수 있다.

단점 ▶ 인풋이 커질수록 비효율적 대가가 심각해진다.

 

비효율적인 Brute force 알고리즘 왜 알아야 하는가?

→ 효율적인 알고리즘을 찾기 위한 출발점이기 때문에 brute force를 확실하게 이해하고 넘어가야 된다 !! 

---

 

▼ my code

def trapping_rain(buildings):
    # 총 담기는 빗물의 양
    total_rain = 0
    
    # 0번째 인덱스와 마지막 인덱스는 생각하지 않아도 되기에 범위를 1 ~ (len-1)로 설정.
    for i in range(1, len(buildings) - 1):
    
        # 현재 위치를 기준으로 양쪽 가장 높은 건물을 찾는다
        max_left = max(buildings[:i])
        max_right = max(buildings[i:])
        
        # 빗물이 채워질 수 있는 높이 = 두 건물 중 더 낮은 건물 높이
        upper_bound = min(max_left, max_right)
        
        # 현재 인덱스에 빗물이 담기는 양을 계산
        if buildings[i] < upper_bound:
            total_rain+= upper_bound - buildings[i]
    
    
    return total_rain

 

 

▼ 코드 보완 사항

 

담기는 빗물을 계산하는 부분에서  코드를 한줄로 줄일 수 있다.

if buildings[i] < upper_bound:
    total_rain+= upper_bound - buildings[i]

 

 # 만약 upper_bound가 현재 인덱스 건물보다 높지 않다면, 현재 인덱스에 담기는 빗물은 0
 total_height += max(0, upper_bound - buildings[i])

 

 

▽ Review

이번 문제는 문제부터 이해하는데 시간이 많이 소요되었다. 시작 방향을 잘못설정하여 생각보다 시간이 많이 소요되었다.

문제풀이를 이해할 때 다른사람들의 풀이도 참고하여 이해를 높일 수 있었다.

문제 풀이 방법을 투포인터와 스택을 이용한 풀이도 있었는데 다음에 새로운 방법으로도 풀이를 정리해 봐야겠다 !