[JavaScript] PCCP 기출문제 2번 - 퍼즐 게임 챌린지
Q. 문제
당신은 순서대로 n개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다. 각 퍼즐은 난이도와 소요 시간이 정해져 있습니다. 당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다. 현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 하면, 게임은 다음과 같이 진행됩니다.
- diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
- diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.
예를 들어 diff = 3, time_cur = 2, time_prev = 4인 경우, level에 따라 퍼즐을 푸는데 걸리는 시간은 다음과 같습니다.
- level = 1이면, 퍼즐을 3 - 1 = 2번 틀립니다. 한 번 틀릴 때마다 2 + 4 = 6의 시간을 사용하고, 다시 퍼즐을 푸는 데 2의 시간을 사용하므로 총 6 × 2 + 2 = 14의 시간을 사용하게 됩니다.
- level = 2이면, 퍼즐을 3 - 2 = 1번 틀리므로, 6 + 2 = 8의 시간을 사용하게 됩니다.
- level ≥ 3이면 퍼즐을 틀리지 않으며, 2의 시간을 사용하게 됩니다.
퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다. 난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.
퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times, 전체 제한 시간 limit이 매개변수로 주어집니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.
* 문제풀이흐름
1. 문제 그대로 level을 1로 초기화하고 1부터 하나씩 증가하며 limit를 넘기지 않는 timeSum이 되면 해당 level return
=> 시간초과 발생
2. Binary Search 탐색으로 접근
3. left는 1, right는 diffs의 가장 큰 값으로
=> Math.max(...diffs)에서 런타임에러 발생하여 diffs.reduce((acc, cur) => Math.max(acc, cur), 1)로 max값 찾음
- 자바스크립트는 함수에 전달할 수 있는 최대 인자 개수(arguments length limit)가 있기때문에 스프레드 연산자보다 하나씩 순차적으로 비교하는 reduce 사용이 안전
4. 클리어 함수를 작성하여 해당 level로 퍼즐을 limit를 넘기지 않고 풀 수 있는지 반환
5. 클리어 함수를 이용하여 level을 이진탐색하여 최소값을 찾아냄
A. 풀이
//Binary Search
function solution(diffs, times, limit) {
let left = 1;
//let right = Math.max(...diffs); => 런타임 에러 발생
let right = diffs.reduce((acc, cur) => Math.max(acc, cur), 1)
let level = 0;
const canClear = (level) => {
let timeSum = 0;
for (let i = 0; i < diffs.length; i++) {
if (diffs[i] <= level) { //내 숙련도로 한번에 풀 수 있는 난이도
timeSum += times[i];
} else { //내 숙련도보다 어려운 난이도
let count = diffs[i] - level;
timeSum += (times[i] + times[i - 1]) * count + times[i];
}
//시간 합이 limit을 넘기면 false
if (timeSum > limit) return false;
}
//해당 level로 limit 시간 내에 퍼즐 클리어 가능
return true;
};
//level이 1~diffs의 가장 큰 값으로 정렬되어있다고 여김
//left <= right : 하나의 답으로 줄여지기 전까지 반복
while (left <= right) {
//중간값 찾기
const mid = Math.floor((left + right) / 2);
if (canClear(mid)) { //퍼즐을 풀 수 있다면 더 작은 값을 찾기
level = mid;
right = mid - 1;
} else { //퍼즐을 풀 수 없다면 더 큰 값에서 찾기
left = mid + 1;
}
}
return level;
}
// 1~될때까지 하나씩 증가하며 탐색
// function solution(diffs, times, limit) {
// let timeSum = 0;
// let level = 1;
// while(true) {
// timeSum = 0;
// for(let i = 0; i < diffs.length; i++) {
// if(diffs[i] <= level) {
// timeSum += times[i]
// } else if(diffs[i] > level) {
// let count = diffs[i] - level
// timeSum += (times[i] + times[i - 1]) * count + times[i]
// }
// if(limit < timeSum) {
// break;
// }
// if(i == diffs.length-1) {
// return level;
// }
// }
// level++
// }
// return level;
// }