프로그래머스: [PCCP 기출문제] 2번 퍼즐 게임 챌린지- javascript(이진탐색)

문제 출처 

정답 풀이 

어제 pccp 풀었을 때 lv1 문제를 무슨 한시간 동안 풀어서 좀 절망적이였는데 

그래도 오늘 lv1, lv2는 각각 30분씩 시간이 들었다. 

오늘 하루는 조금 나한테 위로가 되는 날이다. 

항상 드는 생각이 문제가 복잡하게 느껴져도 단순할 것이다 계속 세뇌를 하며 

예제를 보면서 실제로 단순화 해야 한다. 

이번 문제는 그렇게 풀었다. 

 

그리고, 문제를 풀고 틀렸어도 당황하지 말고, console.log를 통해 어떤 부분이 틀린건지 유추하면서 

고쳐나가면 된다. 사실 그게 진짜 코딩테스트다. 

 

만약 맞았다면, 어떻게 효율성을 더 챙길 수 있을까? 고민해야 한다. 

 

이번 문제는 효율성을 생각해줘야 했다. 

아래는 내가 문제 풀기전에 주석처리로 문제를 정리한 부분이다. 

 

//효율성?
//숙련도를 기준으로 이진탐색으로 해야 한다. 
//- 최저 숙련도 1 
//- 최고 숙련도 100,000
//limit 내에 해당 숙련도로 풀 수 있는지 계산하는 함수

 

정답 코드 

function solution(diffs, times, limit) {
    let start = 1 
    let end = 100000
    while(start <= end){
        let mid = parseInt((start + end) / 2)
        let value = cal(mid, diffs, times, limit)
        if(value){
            end = mid-1 
        }else{
            start = mid+1
        }
    }
    return start
    
    //diffs와 times 을 받아서 limit 이하 시간이면 true 아니면, false 
    function cal(level, diffs, times,limit){
        let result = 0; 
        for(let i=0; i<diffs.length; i++){
            if(level >= diffs[i]){
                result += times[i]
                if(result > limit) return false
            }else{
                let cnt = diffs[i]-level
                let amount = (times[i] + times[i-1] ) * cnt + times[i]
                result += amount 
                if(result > limit) return false
            }
        }
        if(result <= limit) return true 
        else return false
    }
}