강남역에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다.
그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 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을 리턴하는 거죠.
amount += buildings[height_index]*(i-height_index-1)
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]
값이 뒤에나오는 값들보다 층수가 낮을 경우만 생각하고, 높을 경우를 간과했다.
- 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다
- 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이를 구한다
- 그 중 더 낮은 건물의 높이를 구한다
- 그 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다
amount += result - buildings[i]
)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