[JS] 프로그래머스 퍼즐 게임

https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=javascript

프로그래머스

 

이 문제는 구현 + 이진 탐색이었다.

선형 탐색으로 level을 구하기에는 시간 복잡도가 초과될 거 같았다.

(level 선택하는 경우 * 반복문 돌리면서 제한 시간 안에 되는지 확인)

 

따라서 start, end 변수를 사용해서 이진탐색을 이용 -> 로그로 시간 복잡도를 줄였다.

추가로 start <= end로 사용한 이유는 이래야. mid = Math.floor((start + end)/2);의 값이 촘촘하게 구해진다.

즉, start === end의 경우도 구할 수 있다.

 

추가로 start <= end라면 start = mid - 1, end = mid + 1을 해야 한다.

start = mid 또는 end = mid라면 mid = Math.floor((start + end) / 2);가 이전 값이랑 같아져서 무한 반복이 일어날 수 있기 때문이다.

 

최적화를 하자면 end가 지금은 제한 수의 최댓값으로 들어가있는데

diffs의 최댓값으로 해도 된다. (level은 diffs의 최댓값보다 작거나 같아야 최소이므로)

 

코드는 아래와 같다.

 

주의) 등호, start end 값 헷갈리면 answer 변수 사용하자.

 

function solution(diffs, times, limit) {
    let answer = 0;
    const n = diffs.length;
    
    // 제한시간 안에 통과하는지 확인하는 함수
    const isPass = (level) => {
        let time = 0;
        
        for (let i = 0; i < n; i++) {
            const diff = diffs[i];
            const time_cur = times[i];
            const time_prev = i === 0 ? 0 : times[i-1];
            
            if (diff <= level) {
                time += time_cur
            } else {
                time += (diff - level) * (time_cur + time_prev) + time_cur
            }
            
            if (time > limit) return false;
        }
        
        return (time <= limit) ? true : false;
    }
    
    // 선형으로 하면 n^2으로 시간복잡도 초과되므로 이진탐색(투 포인터)
    let start = 1;
    let end = 1000000;
    
    // start < end 아니면 start <= end 확인
    while (start <= end) {
        const mid = Math.floor((start + end) / 2);
        
        const result = isPass(mid);
        
        if (result) {
            answer = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    
    return answer;
}