알고리즘 스터디원 께서 푸셨을때부터 유심히 보며 풀어야겠다 생각했던 문제..

문제 접근

• 그래프로 시도해 보려 했다가 아무리 해도 생각처럼 안되어서 보류

• 주어지는 입력 값을 이용하여 답을 찾아보기로 했다

• 3 0 1 4 를 예로 들면 3에서 단순하게 -0 -1 을 하면 원하는 입력 값을 찾을 수 있다는 점을 이용하였다

• 예전에 사용했던 투포인터 개념을 사용해 보기로 하였다

• 왼쪽 혹은 오른쪽 각각 큰 변수를 임시 변수에 담아 포인터를 이용해 큰값에서 작은 값이라면 빼주고 더 큰값이라면 교체해 주는 방식을 생각했다

• 정돈이 잘 안되어 있는데 의식의 흐름을 따른 낙서였다 ..

• 투 포인터의 특성 상 브레이크 포인트를 l이 r과 같아질때로 하였다

• 포인터가 가르키고 있는 값과 가장 큰 값을 비교하여 가장 큰 값이 더 큰 경우에는 빼서 누적합해주고 그게 아닌 경우에는 가장 큰 값을 교체해주었다

• l의 값과 r의 값을 비교하여 더 작은 방향부터 탐색해주기로 했다 이 기준의 이유는 첫번째 입력 3 0 1 4의 경우 r이 더 큰데 4를 기준으로 계산하게 되면 다른 값이 나오기 때문이다

• 이는 당연한 것이 가장 높은 벽이 하나라면 그 보다 작은 벽을 기준으로 잡아줘야 하기 때문이였다

const fs = require("fs");
const input = fs.readFileSync('example.txt').toString().trim().split('\n')

const [H, W] = input.shift().split(' ').map(Number)

const rain = input.join('').split(' ').map(Number)

let l = 0
let r = rain.length - 1

let left = 0
let rigth = 0

let result = 0

while(l !== r){
  if(rain[l] < rain[r]){
    if(rain[l] >= left){
      left = rain[l]
    }else{
      result = result + left - rain[l]
    }
    l++
  }else{
    if(rain[r] >= rigth){
      rigth = rain[r]
    }else{
      result = result + rigth - rain[r]
    }
    r--
  }
}

console.log(result)

• 접근 방법이 확고해 지고 나니 코드로 구현하는 것은 어렵지 않았다
• 역시 많은 문제를 풀어서 효율적인 접근방법을 찾는 것은 정말 중요한 것 같따