[프로그래머스 Lv2] 퍼즐 게임 챌린지 - Javascript 풀이

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

프로그래머스

---

문제

퍼즐을 풀 수 있는 최소 숙련도를 구하는 문제

 

생각

반복문으로 1부터 100,000까지 모든 숫자를 돌려본다고 했을 때,

diff[i]의 최대 길이 x 퍼즐의 최대 난이도

= 300,000 x 100,000 = 30,000,000,000 (약 300억번)

으로 최대 몇십초가 걸릴 수 있다.

즉, 해당 풀이로는 반드시 시간초과가 발생할 것이다.

 

그래서 떠오른 것이 이분탐색이었다.

이분탐색으로 풀면

diff[i]의 최대 길이 x 이분 탐색 시간

= 300,000 x log₂(100,000) 

= 300,000 x 17 = 510,000

으로 시간이 확 줄어드는 것을 알 수 있다.

 

문제풀이

최소 숙련도 = 0, 최대 숙련도 = 100,000으로 두고

이분 탐색을 통해 퍼즐을 해결할 수 있는 최소 숙련도(mid_lv)를 찾는다.

 

각 퍼즐에 대해, 퍼즐 풀이 시간을 계산해준다.

 

- 숙련도가 퍼즐의 난이도보다 낮은 경우 

solve_time = solve_time + (time_cur + time_prev) * (diffs[i]-mid_lv) + time_cur

 

- 숙련도가 퍼즐의 난이도와 같거나 높은 경우

 

solve_time += time_cur

 

전체 퍼즐을 푸는 시간이 limit이하라면,

현재 숙련도로 모든 퍼즐을 풀 수 있는 것이므로

result에 저장하고 더 낮은 숙련도를 탐색한다.

 

반대로, limit를 초과했다면

숙련도가 부족하다는 뜻이므로 더 높은 숙련도를 탐색한다.

 

 

코드

function solution(diffs, times, limit) {
    let lo = 1, hi = 100000
    let result = hi
    
    while(lo <= hi) {
        let mid_lv = Math.floor((lo + hi) / 2)
        let miss_match = false
        let solve_time = 0
        
        for(let i=0; i<diffs.length; i++) {
            const time_cur = times[i]
            const time_prev = times[i-1]
            
            if ( mid_lv < diffs[i] ) { // 당신의 숙련도가 낮은 경우
                solve_time = solve_time + (time_cur + time_prev) * (diffs[i]-mid_lv) + time_cur
            } else { // 당신의 숙련도가 같거나 높은 경우
                solve_time += time_cur
            }
            
            if ( solve_time > limit ) {
                miss_match = true
                break
            }
        }
        
        if ( miss_match ) lo = mid_lv + 1
        else {
            result = mid_lv 
            hi = mid_lv-1
        }
    }
    
    return result
}