프로그래머스 | Level 2 | 퍼즐 게임 챌린지

Programmers | Level 2 | 퍼즐 게임 챌린지
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Binary Search
Description
당신은 순서대로 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
함수를 완성해 주세요.
Constraints
- 1 ≤
diffs
의 길이 =times
의 길이 =n
≤ 300,000diffs[i]
는i
번째 퍼즐의 난이도,times[i]
는i
번째 퍼즐의 소요 시간입니다.diffs[0]
= 1- 1 ≤
diffs[i]
≤ 100,000 - 1 ≤
times[i]
≤ 10,000
- 1 ≤
limit
≤ 1015- 제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어집니다.
Examples
diffs | times | limit | result |
---|---|---|---|
[1, 2, 3] | [3, 6, 9] | 30 | 3 |
[2, 4, 6, 8] | [1, 3, 5, 7] | 40 | 5 |
Solutions
Code
import java.util.*;
class Solution {
public int solution(int[] diffs, int[] times, long limit) {
int lowLv = 1;
int highLv = Integer.MIN_VALUE; // 난이도의 최댓값으로 초기화
for (int diff : diffs) {
highLv = Math.max(highLv, diff); // 가장 높은 난이도를 찾음
}
int minLv = highLv; // 초기값은 가장 높은 난이도
while (lowLv <= highLv) {
int curLv = (highLv + lowLv) / 2; // 이진 탐색의 중간값
if (canComplete(curLv, diffs, times, limit)) {
minLv = curLv; // 제한 시간 내에 완료 가능한 숙련도
highLv = curLv - 1; // 더 낮은 숙련도에서도 가능한지 탐색
} else {
lowLv = curLv + 1; // 숙련도를 높여 탐색
}
}
return minLv;
}
private boolean canComplete(int lv, int[] diffs, int[] times, long limit) {
long elapsed = 0;
for (int i = 0; i < diffs.length; i++) {
if (diffs[i] <= lv) {
elapsed += times[i]; // 틀리지 않고 해결
} else {
int failures = diffs[i] - lv; // 퍼즐을 몇 번 틀리는지 계산
elapsed += times[i - 1] * failures; // 틀릴 때마다 이전 퍼즐 다시 풀기
elapsed += times[i] * (failures + 1); // 틀린 후 다시 시도
}
if (elapsed > limit) return false; // 제한 시간 초과
}
return true; // 제한 시간 내에 퍼즐 해결 가능
}
}
Approaches
이 문제는 제한된 시간 내에 퍼즐을 해결하기 위해 필요한 최소 숙련도를 구하는 이진 탐색(Binary Search) 문제입니다. 각 퍼즐을 해결할 때, 숙련도에 따라 틀리는 횟수와 해결 시간이 달라지며, 이를 고려해 효율적으로 문제를 해결할 수 있습니다.
1. 문제 분석
주어진 문제는 여러 개의 퍼즐을 제한 시간 내에 해결할 수 있는 최소 숙련도를 구하는 문제입니다. 각 퍼즐에는 고유한 난이도와 소요 시간이 있으며, 플레이어의 숙련도가 퍼즐 난이도에 영향을 미칩니다. 숙련도가 퍼즐 난이도보다 낮으면 플레이어는 퍼즐을 여러 번 틀리게 되며, 이때마다 추가 시간이 소모됩니다. 이 문제를 풀기 위해서는 퍼즐을 해결하는 데 걸리는 시간을 효율적으로 계산하고, 그 시간을 바탕으로 최소 숙련도를 찾아내야 합니다.
문제의 핵심은 숙련도와 퍼즐 난이도의 상관관계를 분석하는 것입니다. 숙련도가 퍼즐 난이도보다 낮을 경우 퍼즐을 여러 번 틀리게 되며, 각 틀릴 때마다 추가적인 시간이 소요됩니다. 특히 퍼즐을 틀리면 다시 그 퍼즐뿐만 아니라 이전 퍼즐까지 다시 풀어야 하는데, 이로 인해 시간이 기하급수적으로 늘어나게 됩니다. 반면, 숙련도가 퍼즐의 난이도 이상일 때는 플레이어가 퍼즐을 틀리지 않고, 소요 시간만큼의 시간만 사용하여 퍼즐을 해결할 수 있습니다.
따라서, 이 문제는 두 가지 중요한 단계로 나눌 수 있습니다. 먼저, 특정 숙련도로 모든 퍼즐을 해결하는 데 걸리는 시간을 계산해야 합니다. 이를 통해 제한 시간 내에 퍼즐을 해결할 수 있는지 판단하게 됩니다. 다음으로는 이진 탐색을 사용하여 가능한 최소 숙련도를 찾아야 합니다. 이진 탐색을 통해 숙련도의 범위를 점진적으로 좁혀가며, 특정 숙련도로 모든 퍼즐을 시간 내에 해결할 수 있는지 확인하는 과정을 반복하게 됩니다.
퍼즐의 개수는 최대 300,000개이며, 제한 시간은 최대 10^15으로 주어지기 때문에, 모든 숙련도를 순차적으로 계산하는 것은 비효율적입니다. 따라서, 이진 탐색을 이용한 효율적인 알고리즘을 사용해야만 제한된 시간 내에 최적의 해를 구할 수 있습니다.
2. 접근 방식
이진 탐색과 시간 계산을 중심으로 문제를 풀어가며 최소 숙련도를 찾는 과정은 다음과 같습니다:
- 이진 탐색 범위 설정:
- 최소 숙련도는 1로 설정합니다.
- 최대 숙련도는 주어진 난이도 배열 중 가장 높은 난이도로 설정합니다.
- 이 범위에서 이진 탐색을 수행합니다.
- 시간 계산 로직:
- 주어진 숙련도로 각 퍼즐을 해결하는 데 걸리는 시간을 계산합니다.
- 퍼즐의 난이도가 숙련도보다 낮거나 같으면, 해당 퍼즐은 제시간에 해결됩니다.
- 난이도가 숙련도보다 높으면, 퍼즐을 여러 번 틀리게 되며, 그만큼 추가 시간이 소요됩니다. 이때 틀릴 때마다 이전 퍼즐도 다시 풀어야 하므로 추가 시간도 고려해야 합니다.
- 시간 초과 여부 판단:
- 현재 설정한 숙련도로 모든 퍼즐을 해결하는 데 걸리는 시간을 계산합니다.
- 만약 그 시간이 제한 시간 내에 해결될 수 있으면, 더 낮은 숙련도로도 가능한지 확인하기 위해 상한선을 줄입니다.
- 반대로 제한 시간을 초과하면, 숙련도를 높여야 합니다.
- 이진 탐색 반복:
- 위 과정을 반복하여 가능한 숙련도의 최소값을 찾아냅니다.
- 탐색 범위를 좁혀가면서 최종적으로 제한 시간 내에 퍼즐을 해결할 수 있는 최소한의 숙련도를 도출합니다.
이 과정은 이진 탐색과 효율적인 시간 계산을 통해 대규모 입력에서도 빠르게 해결할 수 있습니다.
3. 시작 숙련도와 탐색 범위 초기화
퍼즐을 제한 시간 내에 해결하기 위한 최소 숙련도를 찾기 위해 가장 먼저 탐색 범위를 설정합니다. 숙련도의 최솟값은 1로 시작되며, 이는 가장 낮은 경우를 의미합니다. 반면, 숙련도의 최댓값은 주어진 퍼즐들의 난이도 중 가장 높은 값으로 설정합니다. 이는 해당 난이도 이상이면 퍼즐을 틀리지 않고 모두 해결할 수 있기 때문입니다:
int lowLv = 1; // 최소 숙련도는 1로 설정
int highLv = Integer.MIN_VALUE; // 초기값 설정
for (int diff : diffs) {
highLv = Math.max(highLv, diff); // 가장 높은 난이도 찾기
}
int minLv = highLv; // 최소 숙련도를 최대 난이도로 초기화
4. 이진 탐색을 통한 최소 숙련도 탐색
설정한 숙련도 범위 내에서 이진 탐색을 통해 최적의 숙련도를 찾습니다. 탐색 범위의 중간값을 현재 숙련도로 설정하고, 해당 숙련도로 모든 퍼즐을 제한 시간 내에 해결할 수 있는지 확인합니다. 만약 가능하다면, 더 낮은 숙련도로도 가능한지 확인하기 위해 탐색 범위를 줄이고, 불가능하다면 숙련도를 높여 탐색 범위를 조정합니다. 이를 반복하여 최적의 최소 숙련도를 찾아냅니다.
while (lowLv <= highLv) {
int curLv = (highLv + lowLv) / 2; // 중간값 계산
if (canComplete(curLv, diffs, times, limit)) {
minLv = curLv; // 가능한 숙련도 갱신
highLv = curLv - 1; // 더 낮은 숙련도에서 가능한지 확인
} else {
lowLv = curLv + 1; // 불가능하면 숙련도 증가
}
}
이진 탐색 과정에서, 특정 숙련도로 주어진 퍼즐을 제한 시간 내에 해결할 수 있는지를 확인하는 함수가 필요합니다. 각 퍼즐의 난이도가 숙련도보다 낮거나 같으면 바로 해결할 수 있지만, 난이도가 숙련도보다 높을 경우에는 여러 번 틀리게 되어 추가 시간이 소요됩니다. 틀릴 때마다 이전 퍼즐을 다시 풀어야 하므로 그 시간까지 합산하여, 주어진 제한 시간을 초과하는지 여부를 판단합니다.
private boolean canComplete(int lv, int[] diffs, int[] times, long limit) {
long elapsed = 0; // 경과 시간을 저장할 변수
for (int i = 0; i < diffs.length; i++) {
if (diffs[i] <= lv) {
elapsed += times[i]; // 숙련도 이상이면 바로 해결
} else {
int failures = diffs[i] - lv; // 틀린 횟수 계산
elapsed += times[i - 1] * failures; // 이전 퍼즐 재시도 시간 추가
elapsed += times[i] * (failures + 1); // 현재 퍼즐 재시도 시간 추가
}
if (elapsed > limit) return false; // 제한 시간 초과 시 실패
}
return true; // 제한 시간 내 해결 가능 시 성공
}
5. 최소 숙련도 반환
모든 탐색이 완료되면, 최종적으로 계산된 최소 숙련도를 반환합니다. 이 값은 제한 시간 내에 퍼즐을 해결할 수 있는 가장 작은 숙련도를 의미합니다.
// 최소 숙련도 반환
return minLv;
Complexity
- ⏳ TC: O(n log m)
- 💾 SC: O(1)
각 퍼즐의 해결 시간은 난이도와 숙련도에 따라 달라지며, 이진 탐색을 사용해 숙련도를 최적화하는 과정에서 시간 복잡도는 O(n log m)가 됩니다. n
은 퍼즐의 개수, m
는 난이도의 최대값입니다.
- Algorithm
- Binary Search