문제 출처

코딩테스트 연습 > PCCP 기출문제 >[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지
https://school.programmers.co.kr/learn/courses/30/lessons/340212

문제 설명

퍼즐 난이도 배열 diffs, 퍼즐 소요 시간 배열 times, 제한 시간 limit가 주어진다.
현재 퍼즐 난이도 diff, 현재 퍼즐 소요 시간 time_cur, 이전 퍼즐 소요 시간 time_prev, 숙련도를 level 이라 할 때

• diff <= level 이면 time_cur 만큼 시간 사용하여 해결
• diff > level 이면, 퍼즐을 diff - level 만큼 틀리고, 틀릴 때마다, time_cur 만큼 시간 사용 + 이전 퍼즐 시간 time_prev를 사용하여 퍼즐을 다시 풀고 와야한다. 이 후, time_cur 만큼 시간을 사용하여 퍼즐을 해결한다.
  
  
  

접근 방법

해당 문제는 이분 탐색으로 접근해야한다.
1~Max 숙련도 까지 계속 반복하게 되면 시간 복잡도가 O(MAX)까지 커지기 때문에 Max번 반복할 수는 없다.
즉, 이분 탐색으로 접근하는데
(최소 숙련도 1 + 최대 숙련도 Max) /2 = level(숙련도) 로 설정하고
low <= high가 만족하는 동안 계산을 반복한다.

계산 진행 중 퍼즐의 총 풀이 시간인 timeCount가 limit의 이하이면 시간이 남기 때문에 숙련도 최소 값을 낮춘다.(high = mid -1)
반대로 timeCount가 limit의 초과라면 시간이 부족하기 때문에 숙련도 최소 값을 최소 값을 올린다.

이 과정을 통해 숙련도 최소 값을 얻을 수 있다.

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int high = 0;
        int low = 1;
        // 이분탐색으로 풀이
        for(int i = 0; i<diffs.length; i++){ // 각각 low
            high = Math.max(high, diffs[i]);
        }
        while(low <= high){
            int mid = (low + high)/2; // level 설정
            int level = mid;
            long timeCount = 0; // 퍼즐 푸는 총 시간
            for(int j =0; j<diffs.length; j++){
                if(diffs[j] <= level) timeCount += times[j]; // level이 숙련도 이상이면 해당 diff 시간만 추가
                else{// level이 숙련도 미만이면 숙련도 차이 * (이 전 퍼즐의 걸리는 시간들의 총합 + 현재 퍼즐 걸리는 시간) + 현재 퍼즐 걸리는 시간
                    if(j == 0) timeCount += (long) (diffs[j] - level) * (long)(times[j]) + times[j];
                   else{
                       timeCount += (long) (diffs[j] - level)* (long)(times[j] + times[j-1])  + times[j];
                       }
                }
            }
            // 퍼즐 총 풀이 시간이 limit 이하 일 경우 -> high = mid -1; (시간이 남기 때문에 숙련도 최소 값을 낮춤)
            if(timeCount <= limit){
                answer = mid;
                high = mid-1;
            } else{// 퍼즐 총 풀이 시간이 limit 보다 클 경우 -> low = mid +1; (시간이 부족 하기 때문에 숙련도 최소 값을 늘림)
                low = mid+1;
            }
        }
        
        return answer;
    }
}

Review

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        // 이분 탐색으로 접근
        int low = 1;
        int high = 0;
        
        // high 값은 diffs 중 가장 큰 값
        for(int diff : diffs){
            high = Math.max(high, diff);
        }
        
        // low가 high를 넘을 때 까지 이분 탐색 시작
        while(low <= high){
            // 임시 숙련도 최솟값 mid 지정
            int mid = (low+high)/2;
            long timeCount = 0; // 퍼즐을 다 완료 했을 때, 시간
            
            for(int i = 0; i<diffs.length; i++){
                if(mid >= diffs[i]){ // mid가 숙련도 보다 높거나 같을 경우 현재 퍼즐 시간만 더해짐
                    timeCount += times[i];
                }else{ // mid가 숙련도보다 낮을 경우
                    if(i == 0){ // 맨 처음 경우
                        timeCount += (long) (diffs[i] - mid)*(long)(times[i]) + times[i];
                    }else{ // 일반 적인 경우
                        timeCount += (long) (diffs[i] - mid)*(long)(times[i-1] + times[i]) + times[i];
                    }
                }
            }
            // timeCount가 limit 보다 작거나 같은 경우 숙련도를 더 작게 할 수 있기 때문에 high 더 작게
            if(timeCount <= limit){
                answer = mid;
                high = mid -1;
            }else{
                low = mid +1;
            }
            
        }
        return answer;
    }
}

알게된 점

처음 보자마자 이분 탐색으로 풀어야겠다. 생각했지만 다 풀고, 문제를 잘 못 읽어 숙련도가 현재 숙련도에 맞게 수치가 증가하는 방향으로 계산하였다. 아무리 봐도 틀린 곳을 확인하기 어려웠었다.

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int high = 0;
        int low = 1;
        // 이분탐색으로 풀이
        for(int i = 0; i<diffs.length; i++){ // 각각 low
            high = Math.max(high, diffs[i]);
        }
        while(low <= high){
            int mid = (low + high)/2; // level 설정
            int level = mid;
            long timeCount = 0; // 퍼즐 푸는 총 시간
            for(int j =0; j<diffs.length; j++){
                if(diffs[j] <= level) timeCount += times[j]; // level이 숙련도 이상이면 해당 diff 시간만 추가
                else{// level이 숙련도 미만이면 숙련도 차이 * (이 전 퍼즐의 걸리는 시간들의 총합 + 현재 퍼즐 걸리는 시간) + 현재 퍼즐 걸리는 시간
                   timeCount += (long) (diffs[j] - level)* (long)(times[j] + times[j-1])  + times[j];
                    if(timeCount > limit) break;
                    level = diffs[j];
                }
            }
            // 퍼즐 총 풀이 시간이 limit 이하 일 경우 -> high = mid -1; (시간이 남기 때문에 숙련도 최소 값을 낮춤)
            if(timeCount <= limit){
                answer = mid;
                high = mid-1;
            } else{// 퍼즐 총 풀이 시간이 limit 보다 클 경우 -> low = mid +1; (시간이 부족 하기 때문에 숙련도 최소 값을 늘림)
                low = mid+1;
            }
        }
        
        return answer;
    }
}

참고
https://hdbstn3055.tistory.com/222

문제푼 흔적