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

문제

PCCP 기출문제 2번 - 퍼즐 게임 챌린지

https://school.programmers.co.kr/learn/courses/30/lessons/340212

 

 

예시 코드

function solution(diffs, times, limit) {
  const n = diffs.length;
  let left = 1,
    right = 0;
  for (const diff of diffs) {
    right = Math.max(right, diff);
  }

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (canCompletePuzzle(mid)) right = mid;
    else left = mid + 1;
  }

  return right;

  function canCompletePuzzle(level) {
    let totalTime = times[0];

    for (let i = 1; i < n; i++) {
      const wrongCnt = Math.max(diffs[i] - level, 0);
      totalTime += wrongCnt * times[i - 1] + (wrongCnt + 1) * times[i];
      if (totalTime > limit) return false;
    }

    return true;
  }
}

 

풀이

제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하는 문제입니다.

 

숙련도가 올라가면 퍼즐을 푸는데 필요한 시간이 감소하거나 일정하게 유지되는 단조성을 띕니다. 따라서 이분탐색을 통해 효율적으로 해결할 수 있습니다.

 

숙련도의 최솟값은 1이고, 최댓값은 diffs 배열의 원소 중 최댓값입니다. 배열의 크기가 매우 클 수 있기 때문에, Math.max(...diffs) 방식을 사용하는 대신, 일일이 순회하며 최댓값을 찾아야 합니다.

 

게임이 진행되는 과정은 다음과 같습니다.

• diff ≤ level이면, 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
• diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.
• 퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다.

 

이를 코드로 나타내면 이렇습니다.

  function canCompletePuzzle(level) {
    let totalTime = times[0];

    for (let i = 1; i < n; i++) {
      const wrongCnt = Math.max(diffs[i] - level, 0);
      totalTime += wrongCnt * times[i - 1] + (wrongCnt + 1) * times[i];
      if (totalTime > limit) return false;
    }

    return true;
  }

 

diffs[0]은 항상 1이므로, totalTimes를 times[0]으로 초기화합니다.

퍼즐을 순회하며, 이전 퍼즐을 푸는 데 걸리는 시간과 현재 퍼즐을 푸는 데 걸리는 시간을 합산합니다.

 

총 시간이 제한 시간 내이면서 최솟값인 경우를 찾아 반환하면 됩니다.