-
github.com/onlybooks/algorithm-interview
아.. 이거 너무 어렵단
42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
1. 투 포인터를 최대로 이용
O(n^2)으로 풀면 너무 비효율적이다. 그래서 투포인터를 이용한다.
양쪽 벽을 확인하고 더 높은쪽 벽을 기준으로 세워두고 그쪽으로 계속 향하면서 물을 채워나간다.
어렵다 😖 leetcod에도 hard로 분류되어있다.
2. 스택을 이용
거리를 구하고, stack을 이용하였으니 그전에 가장 작았던 벽과의 차이를 구해서 물을 채우는 식으로.. 아래 그림처럼 채워지는 것인듯!
i: 3 stack[-1]: 1distance: 1height[i]: 2 height[stack[-1]] 1 height[top]: 0 top: 2waters: 1i: 6 stack[-1]: 4distance: 1height[i]: 1 height[stack[-1]] 1 height[top]: 0 top: 5waters: 1i: 7 stack[-1]: 4distance: 2height[i]: 3 height[stack[-1]] 1 height[top]: 1 top: 6waters: 0i: 7 stack[-1]: 3distance: 3height[i]: 3 height[stack[-1]] 2 height[top]: 1 top: 4waters: 1i: 10 stack[-1]: 8distance: 1height[i]: 2 height[stack[-1]] 2 height[top]: 1 top: 9waters: 1위지원데이터 엔지니어로 근무 중에 있으며 데이터와 관련된 일을 모두 좋아합니다!. 특히 ETL 부분에 관심이 가장 크며 데이터를 빛이나게 가공하는 일을 좋아한답니다 ✨
'2020년 > 코테' 카테고리의 다른 글
[파이썬 알고리즘 인터뷰] 자신을 제외한 배열의 곱 (0) 2020.12.30 [파이썬 인터뷰 알고리즘] 세 수의 합 (0) 2020.12.22 [파이썬 알고리즘 인터뷰] 배열 (0) 2020.12.20 [파이썬 알고리즘 인터뷰] 가장 킨 팰린드롬 (0) 2020.12.19 [파이썬 알고리즘 인터뷰] 그룹 애너그램 (0) 2020.12.19