[JS] 퍼즐 게임 첼린지

문제

프로그래머스

 

풀이

이 문제와 같이 큰 범위내에서 특정 조건을 만족하는 최소값 혹은 최대값을 찾는 탐색 문제의 경우 완전 탐색을 진행하면 시간초과가 발생할 수 있기에 이분탐색 알고리즘을 이용해 풀이해야 한다.

 

사실 이 문제는 이분탐색 알고리즘만 잘 구현하면 어려운 부분은 없다. 그나마 문제를 틀렸을 경우 시간을 더해주는 로직 구현에 시경을 써야 한다는 점 빼면 그렇게 어려운 문제는 아닌것같다.

 

코드

const solution = (diffs, times, limit) => {
  let [lp, rp] = [1, diffs.reduce((acc, cur) => Math.max(acc, cur), 0)];
    
  const calc = (mid) => {
    let total = 0;
        
    for (let i = 0; i < diffs.length; i++) {
      const levDiff = diffs[i] - mid;
      if (levDiff <= 0) {
        total += times[i];
      }
      else {
        if (i === 0) {
          total += times[i] * levDiff + times[i];
        }
        else {
          total += (times[i] + times[i - 1]) * levDiff + times[i];
        }
      }
      if (total > limit) return total;
    }
    return total;
  }
    
  while (lp < rp) {
    const mid = Math.floor((lp + rp) / 2);
    const res = calc(mid);
        
    if (res <= limit) {
      rp = mid;
    }
    else {
      lp = mid + 1;
    }
  }
  return lp;
}