[프로그래머스] 퍼즐 게임 챌린지

목차

1. 문제
2. 문제 조건
3. 문제 조건 분석
4. 알고리즘
5. 코드

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/340212

2. 문제 조건

n개의 퍼즐을 제한 시간 내에 풀어야 한다.
각 퍼즐은 난이도, 소요시간 정해져 있음 -> diff, time_cur
이전 퍼즐(현재 퍼즐 이전에 풀었던 퍼즐)의 소요 시간 -> time_prev
나의 숙련도 -> level

• diff <= level이면 퍼즐 틀리지 않고 time_cur 만큼 시간 사용해서 퍼즐 해결
• diff > level이면 퍼즐 diff-level만큼 틀린다. 틀릴 때마다 time_cur+time_prev만큼의 시간을 사용. 이후 time_cur만큼의 시간을 사용하여 퍼즐 해결

게임에는 전체 제한 시간 limit이 정해져 있다.
👉 결과적으로 limit 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구해야 한다.

1<=limit<=10^15
1<=n<=300,000
1<=각 퍼즐의 숙련도<=100,000
1<=각 퍼즐의 시간<=10,000

3. 문제 조건 분석

문제를 보고 나서 바로 이분탐색이 생각나야 한다.
이분탐색인 이유는?

모든 숙련도로 다 해본다면 10^5 (모든 숙련도의 개수) x 3x10^5 (모든 퍼즐의 개수) x 퍼즐마다 연산하는 횟수

이미 10^10을 넘어서 완전탐색이 불가하다.
그리고 나의 숙련도의 최솟값을 구한다는 건 완전탐색을 하는 횟수를 줄여 나의 최솟값을 구하면 된다.

10^5 -> log10^5로 줄어들어서 통과 가능한 시간 복잡도가 도출되게 된다.

4. 알고리즘

이분탐색 시작 시에 최저는 1 최대는 100000 값으로 설정하고(조건에 나와있는 최소, 최대의 숙련도) while 문으로 이분탐색을 수행한다.

이때 mid 값의 시간이 limit 를 초과하지 않으면 (적합하면) right = mid -1로 한다.

초과한다면 현재 mid의 숙련도가 작다는 이야기임으로 left = mid + 1로 한다.

나의 경우 이분탐색에서 최종 값을 마지막에
Math.min(left, right)로 도출하는 편이다.

return Math.max(left, right);

5. 코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int left = 1;
        int right = 100000;
        
        while(left<=right){
            int mid = (left+right)/2;
            
            long spentTime = calTime(mid, diffs, times);
            
            if(spentTime > limit){
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        
        return Math.max(left, right);
    }
    
    private long calTime(int level, int[] diffs, int[] times){
        long sum = 0;
        for(int i=0;i<diffs.length;i++){
            int repeat = diffs[i] - level;
            
            if(repeat<=0){
                sum+=times[i];
            } else {
                //반복
                int prevTime =0;
                if(i!=0){
                    prevTime = times[i-1];
                }
                
                sum+=(times[i]+prevTime)*repeat+times[i];
            }
        }
        
        return sum;
    }
}