[programmers/java] 퍼즐 게임 챌린지 - 이분탐색, 시물레이션

1. 문제 개요

- url : https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=java

1.1 퍼즐 게임의 규칙

퍼즐 게임을 플레이하며, 퍼즐을 주어진 순서대로 제한 시간 내에 풀어야 한다. 퍼즐마다 다음과 같은 정보가 주어진다:

• 난이도: diffs[i]
• 소요 시간: times[i]

플레이어의 숙련도를 level이라 할 때, 퍼즐 풀이 규칙은 다음과 같다.

diffs[i] ≤ level	times[i] (한 번에 해결)
diffs[i] > level	diffs[i] - level번 틀리고, 그때마다 times[i] + times[i-1]을 소모한 뒤, 마지막으로 times[i] 소모하여 해결

1.2 문제의 목표

모든 퍼즐을 제한 시간 limit 내에 해결할 수 있도록 하는 **최소 숙련도 level**을 구하는 것이 목표이다.

---

2. 해결 전략

2.1 탐색 방향

이 문제는 특정 level로 퍼즐을 해결 가능한지 판단하는 문제로 귀결된다. 이는 이분 탐색으로 접근 가능하다.

• 탐색 대상: 숙련도 level (정수)
• 탐색 범위: 1부터 max(diffs)까지
• 판단 기준: 주어진 level로 모든 퍼즐을 제한 시간 내에 해결할 수 있는지 여부

2.2 시뮬레이션의 필요성

퍼즐 하나하나의 해결 시간은 숙련도와 이전 퍼즐의 시간에 따라 달라진다. 단순한 누적합 계산으로는 정확한 판단이 어려우므로, 시뮬레이션 방식으로 소요 시간을 계산해야 한다.

---

3. 풀이 과정

3.1 이분 탐색 구조

다음은 숙련도에 대해 이분 탐색을 수행하는 기본 구조이다:

int left = 1;
int right = max(diffs);
while (left <= right) {
    int mid = (left + right) / 2;
    if (check(mid)) {
        answer = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}

3.2 시뮬레이션 함수 구현

각 퍼즐을 순서대로 돌면서 누적 시간을 계산하고, 제한 시간을 초과하는지 여부를 판단한다.

public boolean check(long level, int[] diffs, int[] times, long limit) {
    for (int i = 0; i < diffs.length; i++) {
        int timeCur = times[i];
        int timePrev = (i > 0) ? times[i - 1] : 0;

        if (diffs[i] <= level) {
            limit -= timeCur;
        } else {
            long wrong = diffs[i] - level;
            limit -= (timeCur + timePrev) * wrong + timeCur;
        }

        if (limit < 0) return false;
    }
    return true;
}

---

4. 전체 코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int left = 1, right = getMax(diffs), answer = right;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(mid, diffs, times, limit)) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }

    private boolean check(long level, int[] diffs, int[] times, long limit) {
        for (int i = 0; i < diffs.length; i++) {
            int timeCur = times[i];
            int timePrev = (i > 0) ? times[i - 1] : 0;

            if (diffs[i] <= level) {
                limit -= timeCur;
            } else {
                long wrong = diffs[i] - level;
                limit -= (timeCur + timePrev) * wrong + timeCur;
            }

            if (limit < 0) return false;
        }
        return true;
    }

    private int getMax(int[] diffs) {
        int max = 0;
        for (int d : diffs) max = Math.max(max, d);
        return max;
    }
}

---

5. 시간 복잡도 분석

• 이분 탐색은 O(log(max_diffs)) ≈ 최대 17~18회 반복한다.
• 시뮬레이션은 매번 퍼즐 수 n만큼 반복한다.
• 총 시간 복잡도는 O(n log max_diffs)이다.

입력 범위가 최대 300,000이므로 충분히 효율적인 알고리즘이다.

---

6. 예제 분석

다음은 예제 입력을 바탕으로 숙련도별 소요 시간을 계산한 예이다.

예제 입력

diffs = [1, 5, 3]
times = [2, 4, 7]
limit = 30

숙련도 3일 경우

• 퍼즐 1: 2 (성공)
• 퍼즐 2: (4+2)×2 + 4 = 16
• 퍼즐 3: 7
• 합계: 2 + 16 + 7 = 25 ≤ 30 → 가능

숙련도 3이 최소로 문제를 해결할 수 있는 경우이다.