Problem

1. input: Bar의 높이가 들어있는 배열 height
2. output: 비가 왔을 때 가둬지는 물의 넓이 리턴(그림 참조)

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Idea

물을 가둘 수 있는 Bar는 이전의 Bar보다 높은 Bar이다.

좌 → 우, 우 → 좌, 진행 방향에서 현재 기준 Bar 높이의 최댓값만 저장한 리스트를 만든 후, 두 리스트를 작은값을 기준으로 합치면 물이 가둬진 높이를 구할 수 있다. → Sol1

Solution

1. 물을 가둘 수 있는 Bar 리스트 생성

   • 좌 → 우, 우 → 좌, 진행방향으로 현재 idx 기준 최대높이 리스트 생성
   • 위에서 생성한 두리스트 작은 값 기준으로 merge

   class Solution {
       fun trap(height: IntArray): Int {
           var fromLeft = Array<Int>(height.size){0}
           var fromRight = Array<Int>(height.size){0}
           var leftMax = 0
           var rightMax = 0
           // 좌 -> 우, 우 -> 좌, 현재 idx기준 Bar 높이의 최댓값 리스트 생성
           for (i in height.indices) {
               leftMax = maxOf(leftMax, height[i])
               rightMax = maxOf(rightMax, height[height.size - i - 1])
               fromLeft[i] = leftMax
               fromRight[height.size - i - 1] = rightMax
           }
           // 위에서 만든 두 리스트를 작은 값 기준으로 merge
           var merge = Array<Int>(height.size){0}
           for (i in height.indices) {
               merge[i] = minOf(fromLeft[i], fromRight[i])
           }
           // merge한 리스트에서 Bar의 높이를 빼면 물의 넓이(폭1)
           var answer = 0
           for (i in height.indices) {
               answer += merge[i] - height[i]
           }
           return answer
       }
   }
   

   시간 복잡도: 배열 순회(최대 높이 리스트 생성) + 배열 순회(merge) + 배열 순회(물 계산) = n

   

Point

1. Sol1에서 for문 3개를 2개로 줄일 수 있지만 시간 복잡도는 똑같음