[programmers] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 (java)

✏️ 문제

 

 

🔢 알고리즘

 

#이진탐색 

 

 

🤯 풀이 방법

제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구한다.
최솟값을 구하려면 특정 값에서는 진행이 불가할 때 그 값보단 커야 하고,
가능한 값 중에서는 제일 작아야 한다

그러면 1) 하나씩 올렸다 내린다
2) 특정 기준으로 값을 왔다갔다 해본다 > binary?
  > binary 하는 경우 0부터 가장 큰 diff를 기준으로 시작한다.

 

제출 후 테스트케이스 14에서 틀리는 경우: 숙련도는 1부터 시작해야 한다..

제출 전 테스트케이스 마지막 틀리는 경우: 이진탐색 start <= end 잊지마라...... 음수된다.

 

 

👾 구현 코드 (자바)

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int n = diffs.length;
        
        int start = 1;
        int end = Arrays.stream(diffs).max().getAsInt();
        
        while (start <= end) {
            int mid = (start + end) / 2;
            long takenTime = solve(n, mid, times, diffs, limit);
            
            // 시간이 더 많이 나오면 level값을 늘려야 함
            if (takenTime > limit) {   
                start = mid + 1;
            } else {
                answer = mid;
                end = mid - 1;
            }
        }
        
        return answer;
    }
    
    long solve(int n, int level, int[] times, int[] diffs, long limit) {
        long timeCnt = 0;
        for (int i = 0; i < n; i++) {
            int diff = diffs[i];
            int time_cur = times[i];
            int time_prev = 0;
            if (i > 0) {
                time_prev = times[i - 1];
            } 
            
                
            if (diff <= level) {
                timeCnt += time_cur;
            } else {
                timeCnt += (time_prev + time_cur) * (diff - level);
                timeCnt += time_cur;
            }
                
            if (timeCnt > limit) {
                return timeCnt;
            }
        }

        return timeCnt;
    }

}

 

 

프로그래머스