[Java][프로그래머스][PCCP 기출 문제][Level 2] 퍼즐 게임 챌린지

1. 문제 정보

• 출처: 프로그래머스 PCCP 기출문제 2번 / 퍼즐 게임 챌린지
• 난이도: Level 2
• 분류: 이분 탐색 (Binary Search), 매개변수 탐색 (Parametric Search)

 

 

2. 문제 설명

순서대로 n개의 퍼즐을 제한 시간 내에 해결해야 하는 게임이다. 각 퍼즐은 난이도(diff)와 소요 시간(time_cur)을 가지며, 추가로 이전 퍼즐의 소요 시간(time_prev)도 풀이 시간에 영향을 줄 수 있다.

플레이어의 숙련도(level)에 따라 퍼즐 하나를 풀 때 걸리는 시간은 다음과 같이 결정된다.

1. diff <= level 일 때:
   • 퍼즐을 단번에 해결한다.
   • 소요 시간: time_cur
2. diff > level 일 때:
   • 퍼즐을 총 (diff - level)번 틀린다.
   • 틀릴 때마다 현재 퍼즐 시간 time_cur만큼 소모하며, 이전 퍼즐을 다시 풀고 와야 하므로 추가로 time_prev를 소모한다.
   • 최종적으로 퍼즐을 해결하는 데 걸리는 시간 수식:

최종 소요 시간 계산식: > T = (time_cur + time_prev) * (diff - level) + time_cur

전체 제한 시간 limit가 주어졌을 때, 제한 시간 내에 모든 퍼즐을 해결할 수 있는 숙련도(level)의 최솟값을 구하는 프로그램을 작성해야 한다.

제한사항

• 퍼즐의 수 n <= 300,000
• 퍼즐의 난이도 diffs[i] <= 100,000
• 퍼즐 소요 시간 times[i] <= 10,000
• 제한 시간 limit <= 10^15 (10의 15승 이하의 매우 큰 값이므로 자료형 선택에 주의해야 한다.)

 

 

3. 풀이 전략

이 문제는 단순 선형 탐색으로 숙련도를 1부터 차례대로 늘려가며 확인하면 무조건 시간 초과가 발생한다.

💡 왜 이분 탐색(매개변수 탐색)인가?

만약 선형 탐색을 사용하여 가능한 모든 숙련도(1부터 100,000까지)에 대해 n개의 퍼즐을 검사한다면 최악의 경우 연산 횟수는 다음과 같다.

최악의 경우 연산 횟수: > 300,000 (퍼즐 수) × 100,000 (숙련도 범위) = 300억 번 (3 * 10^10)

이는 통상적인 제한 시간 1~2초 내에 절대로 통과할 수 없는 수치다.
이때 주목해야 할 점은 "숙련도(level)가 높아질수록 전체 퍼즐을 푸는 데 걸리는 시간은 단조 감소(Monotonically Decreasing)한다"는 성질이다.

즉, 최적화 문제(제한 시간 내에 해결할 수 있는 숙련도의 최솟값 구하기)를 결정 문제(특정 숙련도 mid로 제한 시간 내에 해결할 수 있는가?)로 변환하여 탐색 범위를 반씩 줄여나가는 매개변수 탐색(Parametric Search)을 적용할 수 있다.

매개변수 탐색 알고리즘 흐름

1. 탐색 범위 설정:
   • 최소 숙련도 left = 1
   • 최대 숙련도 right = 100,000 (난이도의 최댓값까지만 탐색하면 충분하다.)
2. 이분 탐색 수행:
   • 중간값 mid = (left + right) / 2를 현재 임시 숙련도로 가정한다.
   • canSolve() 헬퍼 메소드를 통해 숙련도가 mid일 때 소요되는 총 시간이 limit 이하인지 검증한다.
   • 성공한다면 (true): 현재 숙련도로 충분히 풀 수 있으므로, 더 작은 숙련도에서도 가능한지 탐색하기 위해 범위를 왼쪽으로 좁힌다. (right = mid - 1, 정답 후보 갱신 answer = mid)
   • 실패한다면 (false): 시간이 부족하므로 숙련도를 더 높여야 한다. 범위를 오른쪽으로 좁힌다. (left = mid + 1)

 

 

4. 정답 코드 (Java)

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        // 탐색할 숙련도의 최소/최대 범위 설정
        int left = 1;
        int right = 100000; // 난이도의 최대 한계치
        int answer = 0;
        
        // 이분 탐색(매개변수 탐색) 시작
        while (left <= right) {
            int mid = (left + right) / 2; // 임시 숙련도(level) 설정
            
            // 해당 숙련도로 제한 시간 내에 해결이 가능한지 판별
            if (canSolve(diffs, times, mid, limit)) {
                right = mid - 1; // 더 작은 숙련도가 존재하는지 좌측 구간 탐색
                answer = mid;    // 최솟값 후보 업데이트
            } else {
                left = mid + 1;  // 숙련도가 너무 낮아 시간이 초과되므로 우측 구간 탐색
            }
        }
        
        return answer;
    }
    
    /**
     * 특정 숙련도(mid)로 제한 시간(limit) 내에 모든 퍼즐을 풀 수 있는지 검증하는 메소드
     */
    private boolean canSolve(int[] diffs, int[] times, int mid, long limit) {
        long prev = 0; // 이전 퍼즐의 소요 시간을 저장하는 변수
        long time = 0; // 누적 총 소요 시간을 저장하는 변수
        
        for (int i = 0; i < diffs.length; i++) {
            // 현재 난이도가 숙련도보다 높은 경우에만 틀리는 횟수(diffs[i] - mid) 계산
            long a = Math.max(diffs[i] - mid, 0);
            
            // 총 소요 시간 누적 계산
            // 단번에 해결하는 경우 (a = 0) -> times[i] 만큼만 소요
            // 틀리는 경우 (a > 0) -> 틀릴 때마다 (이전 퍼즐 시간 + 현재 퍼즐 시간) 소요 후 마지막에 성공 소요 시간 추가
            time += (prev + times[i]) * a + times[i];
            prev = times[i]; // 다음 퍼즐을 위해 현재 소요 시간을 prev에 백업
            
            // 계산 도중 이미 제한 시간을 초과했다면 더 이상 계산할 필요 없이 즉시 실패 반환 (가지치기)
            if (time > limit) return false;
        }
        
        return true;
    }
}

 

 

5. 핵심 포인트

① 자료형 오버플로우(Overflow) 대처

제한 시간 limit이 최대 10^15에 달하는 매우 큰 정수다. 누적 소요 시간을 구하는 공식 중 (prev + times[i]) * a + times[i] 연산 과정에서 일시적으로 큰 값이 발생해 32비트 정수 범위를 아득히 초과할 수 있다.

• 따라서 누적 시간 연산을 담당하는 변수 time과 이전 소요 시간 prev, 그리고 중간 계산식에 들어가는 수치들은 반드시 long 타입으로 연산해 오버플로우를 미연에 방지해야 한다.

② 조기 종료(Short-circuit) 최적화

모든 퍼즐을 끝까지 순회하기 전이라도 누적 시간 time이 limit을 초과하는 순간 바로 false를 반환하도록 설계했다. 이 장치가 없다면 불필요한 루프를 계속 돌게 되어 효율성 테스트에서 큰 손해를 보게 된다.

③ 매개변수 탐색의 정석적인 범위 제어

우리가 도달하고 싶은 목적은 "조건을 만족하는 숙련도의 최솟값"이다. 그렇기 때문에 제한 조건 만족 시 right = mid - 1로 범위를 조여주며 계속해서 최솟값을 갱신해 나가야 최종 루프를 탈출했을 때 가장 정밀한 최적값을 보장받을 수 "있다."

 

 

마치며

이번 문제는 단순 선형 탐색을 적용하면 절대로 풀 수 없지만, 탐색 대상의 결정 조건이 이진 속성(조건 만족 여부)으로 깔끔하게 매핑된다는 특징을 잡아내면 쉽게 정답을 이끌어낼 수 있는 전형적인 매개변수 탐색 문제였다.