[프로그래머스] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 / 자바(Java)

• 문제

• 해설

• 주의점

• 코드

문제

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

프로그래머스

 

---

해설

나의 level과 문제의 diff의 차이에 따라 다른 계산법을 적용해 제한시간보다 작게 나오는 최소 level을 구하는 문제입니다.

 

내 level에 따라 각 문제들의 계산법이 달라지기 때문에 수식으로 모든 값을 계산할 수는 없어 모두 직접 구해보아야 합니다. 하지만 문제의 개수는 300000이고 diff는 최대 100000이므로 level은 1~ 100000이 되어 총 연산횟수가 3*10^10이 되어 너무 많은 연산이 필요합니다.

 

더 빠르게 최소 level을 구하기 위해 이진탐색을 활용합니다. log n 의 시간복잡도를 가져 3*10^5 * log 100000 => 51*10^5 로 더 빠르게 연산 가능합니다.

 

level은 항상 양수이므로 이진 탐색의 범위를 1~100000으로 두고 둘의 합의 절반값을 임시level로 두어 총 경과시간을 계산합니다. 

총 경과시간이 제한시간보다 작아 성공한 경우 answer에 저장해두고 더 작은 성공level이 있는지 탐색하기 위해 이진 탐색의 범위를 최대값을 임시 level-1로 낮춥니다.

총 경과시간이 제한시간보다 커 실패한경우는 성공level을 찾기위해 이진탐색 범위의 최소값을 임시level+1로 바꿉니다.

 

연산 시간을 구할 때 '이전 해결 시간' 을 사용하는 구간이 있으므로 배열 범위를 벗어나는 경우가 없도록 주의해 줍니다.

주의점

• 이전 퍼즐을 푸는 시간이 필요하기 때문에 배열 범위에 주의한다.
• 너무 큰 탐색을 줄이는 방식으로 이진탐색을 사용한다.
• 너무 큰 수의 합이 있으므로 long을 사용한다.

---

코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int low = 1; int high = 100000;
        
        while(low<=high){
            int level = (low+high)/2;
            
            long curTime = getTime(diffs, times,level);
            
            if(curTime<=limit){
                answer = level;
                high = level-1;
            }else{
                low = level+1;
            }
        }
        return answer;
    }
    
    public long getTime(int[] diffs, int[] times, int level){
        long totalTime=0;
        
        for(int i=0;i<diffs.length;i++){
            if(diffs[i]<=level) totalTime+=times[i];
            else{
                if(i==0) totalTime += ((diffs[i]-level) * times[i] + times[i]);
                else totalTime += ((diffs[i]-level) * (times[i]+times[i-1]) + times[i]);
            }
        }
        
        return totalTime;
    }
}