leetcode 42 , 빗물 트래킹

 

문제 : 높이를 입력 받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라

 

입력 : [0,1,0,2,1,0,1,3,2,1,2,1]

 

출력 : 6

 

 

코딩을 할 때마다 하는 생각이지만 문제를 풀 때는 항상 수학적 사고력이 가장 중요한 것 같다.

이 문제에 어떻게 접근을 할 것인가.

이후 나의 사고를 파이썬이라는 언어로 새롭게 만들어내는 것이다.

 

 

 

 

투포인터 알고리즘이란 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다. 

병합정렬의 영역의 기초임 

 

 

한 칸을 기준으로 물을 담을 수 있는 영역은 왼쪽에서 가장 높은 칸, 그리고 오른쪽에서 가장 높은 칸, 그 중 더 작은칸에서 자신이 원래 높이를 뺀 만큼 물을 담을 수 있게 된다. 

 

따라서 자신을 기준으로 왼쪽에서 가장 높은칸을, 오른쪽에서 가장 높은칸을 찾고 그 중 작은 것에서 자신의 높이를 빼주면 된다. 

def solution(height):
  if not height :
    return 0
  
  left = 0
  right = len(height)-1
  max_left = height[left]
  max_right = height[right]
  volume =0 
  while left<right:
    max_left = max(max_left,height[left])
    max_right = max(max_right,height[right])

    if max_left>max_right:
      volume+= max_right-height[right]
      right-=1
    else :
      volume+= max_left-height[left]
      left+=1
  
  return volume

height =[0,1,0,2,1,0,1,3,2,1,2,1]
s=solution(height)
print(s)

 

 

코드 분석

 

if not height:
	return 0

 

리스트에 아무것도 없다면 아무것도 담을 수 없기 때문에 0을 넣어준다.

 

 

volume =0  #넣어 줄 수 있는 물
left =0 투포인터
right = len(height)-1 #투포인터
left_max , right_max = height[left], height[right] #가장 높은 칸

 

while left<right:
  left_max= max(height[left],left_max)
  right_max = max(height[right],right_max)

left 포인터가 right 포인터보다 작은 동안 실행한다. 각각의 포인터가 좌우로 실행되기 때문에 전체 포인터 동안 실행됨

  if left_max<=right_max:
    volume+= left_max-height[left]
    left+=1
  else:
    volume+= right_max - height[right]
    right-=1

왼쪽이 오른쪽보다 작은 경우에는 volume에 left 값에서 자신의 값을 빼서 더해줌. 

아닌 경우에는 반대.