퍼즐 게임 챌린지

오리구이·2025년 3월 12일

코딩테스트

목록 보기

14/14

문제

문제 조건 분석

퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다. 난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.

퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times, 전체 제한 시간 limit이 매개변수로 주어집니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.

제한사항

1 ≤ diffs의 길이 = times의 길이 = n ≤ 300,000

diffs[i]는 i번째 퍼즐의 난이도, times[i]는 i번째 퍼즐의 소요 시간이다.

diffs[0] = 1

1 ≤ diffs[i] ≤ 100,000

1 ≤ times[i] ≤ 10,000

1 ≤ limit ≤ $10^{10}$
제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어진다.

입출력 예

diffs	times	limit	result
$[1, 5, 3]$	$[2, 4, 7]$	$30$	$3$
$[1, 4, 4, 2]$	$[6, 3, 8, 2]$	$59$	$2$

문제 해결 아이디어

숙련도(level)를 증가시킬수록 퍼즐을 해결하는데 걸리는 시간이 단조 감소하는 특성이 있다.
즉, 어떤 숙련도 level이 가능하면, 그보다 높은 level도 가능하다.
이런 경우, 이분 탐색을 적용하면 효율적으로 최적의 값을 찾을 수 있다고 생각했다.
(⚠️ 완전 탐색을 하면 숙련도를 1부터 최대 난이도까지 탐색해야 하므로, 최악의 경우 최대 100,000 × 300,000번의 연산이 필요하다.)

1. 이분 탐색의 범위 설정

숙련도(level)의 최소값 l = 1
숙련도(level)의 최대값 r = max(diffs), 즉 가장 어려운 퍼즐의 난이도

~~처음에 생각없이 숙련도(level)의 최소값을 0으로 초기화해서 삽질했다ㅠ 조건에 분명 나와 있는데..~~

2. 이분 탐색의 범위 설정

curLv = (l + r) / 2를 현재의 숙련도(level)로 가정하고 모든 퍼즐을 해결하는데 걸리는 시간을 계산한다.
계산된 총 시간이 제한 시간을 초과하면 l = curLv + 1로 숙련도(level)를 올려야 한다.
제한 시간 내에 해결이 가능하면 r = curLv로 숙련도(level)를 줄일 수 있는지 확인한다.
l == r이 되면 최적의 숙련도를 찾은 것이다.

3. 퍼즐 해결하는데 걸리는 시간 계산

diffs[i] ≤ curLv 이면 times[i] 만 소요
(퍼즐 난이도가 현재 숙련도와 같거나 낮으면)
diffs[i] > curLv 이면 diffs[i] - curLv번 틀리고, 매번 (times[i-1] + times[i])의 시간이 소요되며 마지막으로 한 번 더 times[i]의 시간이 소요
(퍼즐 난이도가 현재 숙련도보다 높으면)

if (diffs[i] <= curLv) {
	sumT += times[i];
} else if (diffs[i] > curLv) {
	sumT += (diffs[i] - curLv) * (times[i-1] + times[i]) + times[i];
}

코드

class Solution {
    static long limit;
    static int maxV = 0;
    
    public int solution(int[] diffs, int[] times, long limit) {
        for (int i = 0; i < diffs.length; i++) {
            maxV = Math.max(maxV, diffs[i]);
        }
        int l = 1;
        int r = maxV;
        int ans = 0;
 
        while(l <= r) {
            int curLv = (l + r) / 2;
            long sumT = 0;
            for (int i = 0; i < diffs.length; i++) {
                if (diffs[i] <= curLv) {
                    sumT += times[i];
                } else if (diffs[i] > curLv) {
                    sumT += (diffs[i] - curLv) * (times[i-1] + times[i]) + times[i];
                }
            }  
            if (sumT > limit) {
                l = curLv + 1;
            } else if (sumT <= limit) {
                r = curLv - 1;
                ans = curLv;
            }
        }
        return ans;
    }
}

시간 복잡도 분석

이분 탐색을 사용하여 O(log(max(diffs))) 번 반복하며, 각 반복에서 O(n)번 연산하므로 전체 시간 복잡도는 O(n log max(diffs))가 된다.

max(diffs)는 최대 100,000이므로 log 값은 약 17

n의 최대값이 300,000이므로 최악의 경우 약 5,100,000번 연산으로 충분히 해결 가능하다.

오리구이

이전 포스트