[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

문제 설명

• 당신은 순서대로 n개의 퍼즐을 제한 시간 limit 내에 해결하는 게임을 하고 있습니다.
• 각 퍼즐은 다음과 같은 속성을 가집니다.
  • diffs[i]: i 번째 퍼즐의 난이도
  • times[i]: i번째 퍼즐을 푸는 데 걸리는 시간
• level에 따라 퍼즐을 푸는 시간이 달라집니다:
  1. diff <= level인 경우
     • 퍼즐을 틀리지 않고, times[i]만큼의 시간만 사용
  2. diff > level인 경우
     • diff - level번 틀리고, 틀릴 때 마다 times[i-1] + times[i] 만큼의 시간이 소요
     • 총 (diffs[i] - level) * (times[i - 1] + times[i]) + times[i] 의 시간이 소요
• 제한 시간 limit내에 모든 퍼즐을 해결할 수 있는 최소한의 level을 반환합니다.

문제 풀이

Binary Search

limit 시간 내에 모든 퍼즐을 해결할 수 있는 최소한의 level을 찾는 문제이므로, level을 기준으로 해당 퍼즐을 풀 수 있는지 없는지를 판별하며, 이분 탐색으로 해결할 수 있다.

1. canSolvePuzzle(level)
   • 주어진 level으로 limit 시간내에 문제를 해결할 수 있는지 판별
2. 이분 탐색으로 최소한의 level을 찾기
   • left: diffs[0]은 항상 1이므로, 1을 기준으로 시작
   • right: diffs의 가장 높은 값을 기준으로 시작
   • mid를 중간 level로 설정하고 canSolvePuzzle(mid)로 검증
     • 퍼즐을 풀 수 있는 경우, 더 낮은 level이 가능한지 확인이 필요하므로 right = mid
     • 퍼즐을 풀 수 없는 경우, 더 높은 level이 필요하므로 left = mid + 1

export function puzzleGameChallenge(diffs: number[], times: number[], limit: number): number {
  function canSolvePuzzle(level: number): boolean {
    let currentTime = 0;
    for (let i = 0; i < diffs.length; i++) {
      if (i === 0 || diffs[i] <= level) {
        currentTime += times[i];
      } else {
        currentTime += (diffs[i] - level) * (times[i - 1] + times[i]) + times[i];
      }
      if (limit < currentTime) {
        return false;
      }
    }
    return true;
  }
 
  let left = 1;
  let right = diffs.reduce((prev, diff) => Math.max(prev, diff), 1);
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (canSolvePuzzle(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

// 제출을 위해 함수 이름을 `solution`으로 변경
function solution(diffs, times, limit) {
  function canSolvePuzzle(level) {
    let currentTime = 0;
    for (let i = 0; i < diffs.length; i++) {
      if (i === 0 || diffs[i] <= level) {
        currentTime += times[i];
      } else {
        currentTime += (diffs[i] - level) * (times[i - 1] + times[i]) + times[i];
      }
      if (limit < currentTime) {
        return false;
      }
    }
    return true;
  }
 
  let left = 1;
  let right = diffs.reduce((prev, diff) => Math.max(prev, diff), 1);
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (canSolvePuzzle(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

복잡도

• 시간 복잡도: $O(n + n \cdot log_2{(\max(\text{diffs}))}$
• 공간 복잡도: $O(1)$