[Algorithms] 파이썬 알고리즘 인터뷰 #8, Leetcode 42번: Trapping Rain Water

원래 이번 방학때 국민대 대회 , 컴퓨터비전 강의듣고 정리해놓고 테니스 치려고 했는데 혹시나 국민대 대회가 떨어질까봐 걱정되는 마음에 현대모비스에서 하는 알고리즘 대회를 신청했다.. 자율주행 관련되어서 연구개발하는 모비스에서 하는 대회이기도 하고, 언젠가는 한번 이런 알고리즘 대회 나가보고 싶어서 그냥 신청했다ㅋㅋ 모비스 대회 하기전에 전에 사놓은 파이썬 알고리즘 인터뷰에 있는 문제들 다는 못풀어도 각 단원에 있는 문제 절반은 풀어보고 싶어서 다시 시작했다.

이번 문제는 작년에 올린 글에 이어서 책 8번문제 리트코드 42번 문제다. 

내가 스스로 풀지는 못했고 고민하다가 책의 해설에 도움을 받았다.. 

책에서는 투 포인터와 스택 두가지 해결방법으로 풀어놓았는데, 스택은 뒤에 단원에서 나오기도하고 한문제에 너무 많은 시간을 투자할 수 없을거같아 투 포인터 해설 부분을 참고했다. 

#투 포인터 활용

이 투포인터 해결방법의 요지는 가장큰 기둥(?)을 중심으로 양옆에 left 와 right라는 포인터를 지정하고, left와 right를 가장 큰 기둥 방향으로 진행시키면서 지나온 구간에서 가장 큰 기둥을 기억하는 방식이다. 

 

class Solution:
    def trap(self, height: List[int]) -> int:
        volume = 0
        # 기둥 왼쪽의 포인터를 0으로 초기화
        left = 0
        # 기둥 오른쪽의 포인터를 배열 가장끝으로 초기화
        right = len(height)-1
        
        # 양 옆 구간의 가장큰 기둥을 저장하는 left_max와 right_max을 선언하고, 초기화
        left_max = height[left]
        right_max = height[right]
        
        while(left<=right):
        	#이전의 left_max와 비교하여 구간의 가장큰 기둥으로 max값을 갱신해준다
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])
            
            # left_max와 right_max를 비교하면서 큰값이 있는 쪽에서 volume을 더해준다
            if(left_max<=right_max):
                volume += left_max-height[left]
                left = left+1
            else:
                volume += right_max-height[right]
                right = right-1
                    
        return volume