[leetcode] 빗물 트래핑

문제 내용

예전 NHN 코딩테스트 문제에서 봤던 기억이 얼~추 나는거 같습니다!?

문제 해결 의식의 흐름

뚫어져라 쳐다보다 보니 우뚝 서 있는(?) 부분이 키 포인트가 될것 같았습니다.
가장 높은 부분을 기준으로 잡자! 라는 생각을 하다보니
자연스럽게 모든 배열을 순회하기 위해 기준의 왼쪽과 오른쪽으로 나누게 됬습니다.
왼쪽에서부터 기준까지 이동하면서 빗물을 세고,
오른쪽에서 기준까지 이동하면서 빗물을 센 뒤에 합치면 되겠구나! 라는 생각을 하고
accept를 받게 됬습니다.

문제 해결

1. 먼저 우뚝 서있는(= 배열에서 가장 큰 값) 기준의 인덱스를 받아와야 했습니다.
   • 만약 가장 큰 값이 두개라면? 이라는 예외가 생겼지만 가장 먼저 얻은 인덱스를 사용해서 진행하면 문제가 없었습니다.
2. 높이의 최대값을 갱신하면서 만약 현재 높이가 최대값보다 작은 경우 최대값 - 현재 높이를 답에 더해준다.
3. 좌,우에서 진행한 후에 값을 더해준다.

정답 코드

var trap = function(height) {
    let answer = 0;
    // 가장 큰 값의 인덱스를 찾는다.
    let maxIndex = height.indexOf(Math.max(...height))
    let max_height = -1
    // 0부터 기준의 인덱스까지 빗물을 센다.
    for (let i = 0; i < maxIndex; i++) {
        if (max_height <= height[i]) {
            max_height = height[i]
            continue
        }
        
        answer += max_height - height[i]
    }
  
    // 비교할 값 초기화
    max_height = -1
    
  	// 끝부터 기준까지 이동하며 빗물을 센다
    for (let i = height.length - 1; i > maxIndex; i--) {
        if (max_height <= height[i]) {
            max_height = height[i]
            continue
        }
        
        answer += max_height - height[i]
    }
    
    return answer
};

개선 방향

투포인터처럼 풀려고 했지만 위의 풀이는 사실 한번에 진행할 수 있는 코드를,
왼쪽, 오른쪽 for문으로 나눠서 두번에 풀고 있는 느낌이었습니다.
직접 최대값을 찾는 수고를 덜 수 있도록
맨 왼쪽의 값과 맨 오른쪽의 값을 비교하면서 진행하면 투포인터처럼 풀 수 있었습니다.

var trap = function(height) { 
    let answer = 0;
    let left_max = -1
    let right_max = -1
    let left = 0
    let right = height.length - 1
    // 만약 left와 right가 만나게 된다면, 그 지점이 가장 높은 지점일것이다.
    while (left < right) {
      	// 최대값을 계속해서 갱신해준다.
        left_max = Math.max(left_max, height[left])
        right_max = Math.max(right_max, height[right])
      
        // 왼쪽 최대값이 오른쪽 최대값보다 작으면 left 를 더해준다.
        if (left_max <= right_max) {
            answer += left_max - height[left]
            left++
        }
      
        // 반대의 경우
        else {
            answer += right_max - height[right]
            right--
        }
    }
    
    return answer
};

문제 출처

https://leetcode.com/problems/trapping-rain-water/submissions/