🧩 [PCCP 기출문제] 2번 퍼즐 게임 챌린지 JAVA 풀이 및 복기

퍼즐 게임 챌린지 JAVA 코딩테스트 문제 풀이 복기 기록

 

1. 문제 이해

• 문제 유형: 이분 탐색 + 시뮬레이션
• 입력: diffs[] (난이도 차이), times[] (걸리는 시간), limit (총 시간 제한)
• 목표: 최소 level을 찾아, 퍼즐 시간을 limit 이하로 만들기

중요 포인트

• 단순 반복문으로 1~300,000까지 탐색하면 시간 초과
• level 증가 → diffs[i] - level 감소 → 소요 시간 감소
• 즉, 단조성(monotonicity) 존재
• 이분 탐색(Binary Search)의 핵심 전제 조건인 단조성(Monotonicity)은 탐색 범위 내에서 값이 일정한 방향으로 증가하거나 감소하는 성질을 의미

---

2. 문제 접근 방식

1. 완전 탐색으로 먼저 생각
   • level 1~300,000을 돌면서 체크 → 시간 초과
2. 단조성 관찰
   • level ↑ → 소요 시간 ↓
   • 조건 만족 여부 YES/NO 판별 가능
3. 이분 탐색 떠올림
   • 조건을 충족하는 최소 level을 찾는 문제 → Lower bound 유형
4. 검증 함수 작성
   • puzzleCheck(level)
   • level을 넣으면 소요 시간을 계산하고, limit 초과 시 -1 반환

---

3. 핵심 힌트/착안점

• 단조성 확인 → 이분 탐색 가능
• mid가 정답 후보인지 확인 → YES → answer 갱신, 오른쪽 범위 줄이기
• 자료형 주의 → 소요 시간이 long 범위 가능
• 이전 시간 처리(첫번째 퍼즐을 바로 풀지 못하는 Case): 첫 번째 퍼즐은 이전 퍼즐이 없으므로 time_prev를 0으로 처리하거나 조건문으로 예외 처리 필요

---

4. 구현 흐름 요약

1. left = 1, right = 100000, answer = right
2. while(left <= right) 반복
   • mid = (left + right) / 2
   • puzzleCheck(mid) 결과 확인
     • 성공 → answer = mid, right = mid - 1
     • 실패 → left = mid + 1
3. 종료 후 answer 반환

실제 구현 소스코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;

        // 처음부터 끝까지 돌린다 -> 시간초과 
        // diff
       /** for(int level=1; level<=300000; level++){
            
            long result = puzzleCheck(level, diffs, times, limit);
            
            if(result != -1) return level;
        }
        **/
        
        int left = 1;
        int right = 100000;
        
        while (left <= right) {
            
            int mid = left + (right - left) / 2;
            
            long result = puzzleCheck(mid,diffs,times,limit);
            //System.out.println ("mid : "+mid+ " result "+result);
            
            if(result != -1) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            
        }
        return answer;
    }
    
    public static long puzzleCheck(int level, int [] diffs, int [] times, long limit){
                
        int time_prev = 0;
        long time_total = 0;
        
        for(int i=0;i<diffs.length;i++){
            //System.out.println("level : "+ level + " time_total "+time_total+" time_prev" + time_prev);

            if(limit < time_total) return -1;
            else {
                int count = diffs[i] - level;
                
                if(count <= 0) {
                    time_total += times[i];
                } 
                else {
                    time_total += (times[i]+time_prev) * count + times[i];
                    
                }
                time_prev = times[i];
            }      
        }

        if(limit < time_total) return -1;
        return time_total;
        
    }
}

---

5. 회고 및 개선점

• ✅ 완전탐색(선형탐색) 시, 시간초과 문제 → 단조성 발견 후 이분 탐색 적용
• ⚠️ 주의할 점
  • 자료형 오버플로우: 곱셈 시 long 사용
• 향후 개선 포인트
  
  • puzzleCheck()에서 불필요한 변수 제거
  • 테스트 케이스로 단조성 검증
  • 범위를 더 좁게 설정 가능
  • 시간복잡도 계산 후 탐색 접근 필요
  • 단조성 패턴 발견 → 완전 탐색 → 시간 초과 → 이분 탐색 떠올려볼것
  • 다시 풀어볼 문제!
  • 비슷한 유형인 백준의 '랜선 자르기'나 '나무 자르기' 문제도 도전