[Algorithm] Brute Force - 강남역 폭우

hyo_·2021년 4월 28일
0

알고리즘

목록 보기
3/3

Brute Force 알고리즘 예제

강남역 폭우

문제

강남역에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다.

그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 trapping_rain을 작성해 보려고 합니다.

함수 trapping_rain은 건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴해 줍니다.

예를 들어서 파라미터 buildings로 [3, 0, 0, 2, 0, 4]가 들어왔다고 합시다. 그러면 0번 인덱스에 높이 33의 건물이, 3번 인덱스에 높이 22의 건물이, 5번 인덱스에 높이 44의 건물이 있다는 뜻입니다. 1번, 2번, 4번 인덱스에는 건물이 없습니다.

그러면 아래의 사진에 따라 총 1010 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain 함수는 10을 리턴하는 거죠.

접근

  1. 모든 경우의 수를 다 사용하기 위해 이중 for문??.. ❌(너무 복잡하게 생각함)
  2. 앞쪽에서 층수가 1 이상인 건물과 그 건물 뒤에나오는 건물들 중 지정한 건물보다 높은 층 수를 가진 빌딩을 찾아앞에 있는 빌딩의 층 수로 빗물의 총량을 계산하고 그사이에 있는 건물의 층수를 빗물의 총량에서 뺀다. ❌
    • height_index 라는 변수를 생성해 0으로 초기화한다.
    • for문을 돌면서 building[height_index] 보다 높은 건물이 나오면 amount += buildings[height_index]*(i-height_index-1)
    • building[height_index] 보다 낮은 건물이면 amount -= buildings[i]
    • 맨 첫번째 건물 혼자서는 빗물을 담을 수 없으므로 if height_index!=i조건을 충족할 시 위의 두 조건을 실행한다. (height_index가 i와 똑같을 때는 0일 때 밖에 없다.)
def trapping_rain(buildings):
    amount = 0 
    height_index = 0  
    for i in range(len(buildings)):
        if height_index!=i:
            if buildings[height_index] <= buildings[i]:
                amount += buildings[height_index]*(i-height_index-1)
                height_index = i
            else:
                amount -= buildings[i]

    return amount
# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

=> 두번째 방식으로 하면 print(trapping_rain([3, 0, 0, 2, 0, 4]))값은 제대로 나오지만 print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))값은 이상하게 나온다.

잘못 생각한 점

building[height_index] 값이 뒤에나오는 값들보다 층수가 낮을 경우만 생각하고, 높을 경우를 간과했다.

힌트

  • 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다
  • 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이를 구한다
  • 그 중 더 낮은 건물의 높이를 구한다
  • 그 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다
  1. for문을 돌면서 각각의 층수에 물이 얼마나 받아질 수 있는지 계산한다.⭕
    • buildings 리스트를 index기준으로 반으로 나누어 각각 최대 값을 찾아 left, rihgt 변수에 저장
    • left, right 중 더 낮은 층수를 찾아 result 변수에 저장
    • result 값이 buildings[i] 보다 높을 때만 amount 값에 저장( 빌딩이 있는 부분은 물로 채우지 못하기 때문에 amount += result - buildings[i] )

code

def trapping_rain(buildings):
    amount = 0
    # 총 담기는 빗물의 양을 변수에 저장
    for i in range(1, len(buildings) - 1):
        left = max(buildings[:i])
        # 현재 건물보다 왼쪽에 있는 건물들 중 가장 높은 건물의 층 수 저장
        right = max(buildings[i:])
        # 현재 건물보다 오른쪽에 있는 건물들 중 가장 높은 건물의 층 수 저장

        result = min(right, left)
        # 선택된 두 건물 중 더 낮은 건물 층 수 저장
        if result > buildings[i]:
            # 저장 된 층 수 보다 현재 건물이 더 낮을 경우에만 물이 찰 수 있다.
            amount += result - buildings[i]
            # 저장된 층수에서 현재 건물의 층수를 뺀 나머지 부분을 물로 채운다. -> amount 변수에 나머지 층 수 값 저장

    return amount


print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

결과 값




def trapping_rain(buildings):
    # 총 담기는 빗물의 양을 변수에 저장
    total_height = 0

    # 리스트의 각 인덱스을 돌면서 해당 칸에 담기는 빗물의 양을 구한다
    # 0번 인덱스와 마지막 인덱스는 볼 필요 없다
    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)

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

    return total_height

# 테스트
print(trapping_rain([0, 3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

내 코드 리뷰

  • 두 번째 방식으로 코드를 짤 때 두 건물 사이의 총 빗물의 합을 측정하고 건물들의 층수 값을 빼려고 해서 더 헷갈렸던 것 같다. 힌트를 확인한 뒤, 두 건물 사이의 총 빗물을 한번에 계산하기 보다 각각의 건물이 담을 수 있는 빗물의 양을 측정한 뒤 합치는게 좋다는 것을 알았다.
  • if result > buildings[i]:amount += result - buildings[i] 부분을 간결하게 답에서는 total_height += max(0, upper_bound - buildings[i])한 줄로 나타내었다.
  • 결괏값 도출에 신경쓰느라 모든 경우의 수를 차근차근 생각해 보지 못하고 급하게 코드를 적어나갔던 것이 오히려 시간을 더 오래 걸리게 했다. 앞으론 코드 작성 전 하나하나 경우를 어떻게 해결할지 생각해보고 코드 작성을 해야겠다!

참고

코드잇 - 알고리즘의 정석 강의 예제
https://www.codeit.kr/courses/algorithms

profile
🎓의지적인 삶을 살자!😊

0개의 댓글