Algorithm[Trapping Rain - LeetCode]

각 인덱스에 따른 블럭의 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

입력
0 1 0 2 1 0 1 3 2 1 2 1
출력
6

✏️ 문제풀이 1

물을 포함한 모든 박스의 크기에서 물이 아닌 박스의 크기를 뺀다.

• 모든 박스의 크기: 1층 박스 + 2층 박스 + 3층 박스
• 1층 박스의 양: 오른쪽에서 보았을때 처음으로 나오는 1층짜리 박스의 인덱스 - 왼쪽에서 보았을때 처음으로 나오는 박스의 인덱스 +1
  2층…
• 물을 제외한 박스의 크기: sum(height)

height = list(map(int,input().split()))
reversed_list = height[::-1]
max_height = max(height)
block = 0


for i in range(1, max_height+1):
    left = height.index(i)
    right = len(height) - reversed_list.index(i) - 1
    block += right - left + 1

print(block-sum(height))

Time Complexity: O(n^2)

✏️ 문제풀이 2 (Two Pointers)

가장 높은 기둥을 기준으로 좌측과 우측 두 부분으로 나누고, 양쪽에서 가장 높은 기둥으로 각각 접근하며 물의 부피를 세어 나간다.

height = list(map(int,input().split()))

left, right = 0, len(height)-1
left_max, right_max = height[left], height[right]
volume = 0
top_index = height.index(max(height)) 

while left < top_index:
    if height[left] > left_max:
        left_max = height[left]
    else:
        volume += left_max - height[left]
    left += 1

while top_index < right:
    if height[right] > right_max:
        right_max = height[right]
    else:
        volume += right_max - height[right]
    right -= 1
    
print(volume)

Time Complexcity: O(n)

✏️ 문제풀이 3 (Stack)