[Javascript] 프로그래머스 - 퍼즐 게임 챌린지

문제 설명

퍼즐 게임에서 주어진 차이와 시간을 기준으로 제한 시간 내에 도전 과제를 완료하기 위한 최적의 기준값을 찾는 문제입니다.

• 각 퍼즐의 난이도 차이는 배열 diffs로 주어집니다.
• 각 퍼즐을 해결하는 데 소요되는 기본 시간은 배열 times로 주어집니다.
• 제한 시간 limit 내에서 도전 과제를 완료하려면, 기준값을 적절히 조정하여 퍼즐의 난이도를 낮춰야 합니다.
• 최적의 기준값을 계산하여 반환합니다.

---

제한사항

1. 퍼즐 정보
   • 퍼즐 개수: diffs.length는 1 이상 100,000 이하.
   • 각 퍼즐의 난이도 차이: 1 이상 10^15 이하.
   • 각 퍼즐의 소요 시간: 1 이상 10^9 이하.
2. 제한 시간
   • 제한 시간 limit은 1 이상 10^18 이하.

---

해결 방법

알고리즘: 이진 탐색

1. 탐색 범위 설정
   • 기준값(mid)을 1부터 10^15까지로 설정합니다.
2. 기준값 검증
   • 각 기준값에 대해 주어진 난이도 차이와 시간을 이용해 총 사용 시간을 계산합니다.
   • 현재 난이도 차이가 기준값보다 크다면, 초과 부분을 줄이기 위해 추가 시간을 계산합니다.
   • 제한 시간(limit)을 초과하는 경우 기준값을 높이고, 초과하지 않는 경우 기준값을 낮춥니다.
3. 이진 탐색 수행
   • 기준값이 제한 시간 내에서 조건을 만족하도록 탐색 범위를 조정합니다.
   • 최적의 기준값을 반환합니다.

---

시간 복잡도

1. 이진 탐색의 반복 횟수: O(log⁡(r)), r=10^15
2. 각 반복에서 퍼즐 배열 탐색: O(n), n은 퍼즐 개수
3. 총 시간 복잡도: O(n×log⁡(r))

---

구현 코드

function solution(diffs, times, limit) {
  let answer = Infinity;

  let left = 1;
  let right = Math.pow(10, 15);

  while (left <= right) {
    const mid = Math.floor((right + left) / 2);
    let usageTime = 0;
    let timePrev = 0;

    for (let i = 0; i < diffs.length; i++) {
      const failCount = Math.max(diffs[i] - mid, 0);
      usageTime += failCount * (times[i] + timePrev) + times[i];

      if (usageTime > limit) {
        break;
      }

      timePrev = times[i];
    }

    if (usageTime <= limit) {
      answer = Math.min(answer, mid);
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return answer;
}