[코드잇][알고리즘의 정석]토픽 3: Brute Force-06. 강남역 폭우

[코드잇][알고리즘의 정석]토픽 3: Brute Force-06. 강남역 폭우

 

링크: https://www.codeit.kr/learn/courses/algorithms/1141

코딩이 처음이라면, 코드잇

 

---

문제

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

그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 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을 리턴하는 거죠.

이번에는 파라미터 buildings로 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]가 들어왔다고 합시다. 그러면 아래의 사진에 따라 총 66 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain 함수는 6을 리턴하는 거죠

이 정보를 기반으로, trapping_rain 함수를 작성해 보세요!

예시

 

 

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

 

10
6

---

제출한 답

처음에 제출한 답(정상적으로 작동함)

def trapping_rain(arr):
    
    left = -1
    right = 0
    rain = 0
    
    while right <= len(arr)-1:
        #왼쪽,오른쪽 설정
        for i in range(left+1,len(arr)):
            # print('for','i',i,'left', left,'arr[i]', arr[i])
            if arr[i] != 0:
                if left == -1: 
                    left = i
                elif arr[i] >= arr[left]:
                    right = i
                    break
        else:
            if left <= len(arr)-4:
                left += 1
                right = left + 1
                continue
            else: break
        
        #사이에 빗물 채우기
        if right > left + 1:
            m = min(arr[left],arr[right])
            for i in range(left+1,right):
                rain += (m - arr[i])
        left = right
        right += 1
    return(rain)
# 테스트
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(arr):
    rain = 0
    for i in range(1,len(arr)-1):
        #왼쪽 건물 구하기
        left = 0
        for l in range(1,i):
            if arr[l] > arr[left]:
                left = l
        if arr[i] >= arr[left]: #더 큰 숫자x
            continue
            
        #오른쪽 건물 구하기
        right = i+1
        for r in range(i+2, len(arr)):
            if arr[r] > arr[right]:
                right = r
        if arr[i] >= arr[right]:#오른쪽에 arr[i]보다 더 큰 숫자 없음
            continue

        m = min(arr[left],arr[right])
        if m > arr[i]:
            rain += m - arr[i]
    
    return(rain)
# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

 

알고리즘은

1. 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다
2. 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이를 구한다
3. 그 중 더 낮은 건물의 높이를 구한다
4. 그 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다

의 순서

 

 

이번 건 조금 어려웠다.

푸는 종종 내가 원하는 값이 나오는지 디버깅해서 확인해야겠다.