[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 - Python/JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=python3

프로그래머스

 

[문제 간단 요약]

1. 퍼즐 문제를 제한시간 안에 해결하기 위한 숙련도의 최소 값 구하는 문제

2. 숙련도보다 어려운 난이도의 문제 경우 이전 문제를 (난이도 - 숙련도) 만큼의 이전 문제를 해결 필요

    즉, 난이도가 높은 경우 : (난이도 - 숙련도) * (이전 문제 해결 시간 + 현재 문제 해결 시간) + 현재 문제 해결 시간 필요

 

[문제 해결 방안]

- 문제 제한사항 확인 필요 (문제의 갯수가 최대 30만개일 경우 시간 초과 가능성 고려)

  - 난이도를 하나씩 올리는 단순 구현의 경우 시간초과 발생!

  - 특정 여러 정답이 될 수 있는 값 중 최적의 하나의 값을 선택 하는 것으로 탐색 문제 -> 이진 탐색으로 문제 해결

문제 제한사항

 

[문제 해결 코드 - Python]

def solution(diffs, times, limit):
    s,e = 1, max(diffs)+1
    
    while e > s:
        chk_level = (e+s) // 2
        chk_time = 0
        
        for i in range(len(diffs)):
            if i == 0:
                time_cur=times[0]
                time_pre=0
            else:
                time_cur=times[i]
                time_pre=times[i-1]
            used_time = time_cur + max(0,(diffs[i]-chk_level))*(time_cur+time_pre)
            chk_time += used_time
            
        if chk_time <= limit:
            e=chk_level
        else:
            s=chk_level+1
    return s

 

[문제 해결 코드 - JavaScirrpt]

function solution(diffs, times, limit) {
    let s = 1;
    let e = 100000+ 1;
    while (e > s) {
        let chk_level = Math.floor((e + s) / 2);
        let chk_time = 0;
        
        for (let i = 0; i < diffs.length; i++) {
            let time_cur = times[i];
            let time_pre = 0
            if (i !== 0) {
                time_pre = times[i - 1]
            }
            let used_time = time_cur + Math.max(0, (diffs[i] - chk_level)) * (time_cur + time_pre);
            chk_time += used_time;
        }

        if (chk_time <= limit) {
            e = chk_level;
        } else {
            s = chk_level + 1;
        }
    }
    return s;
}

 

이진 탐색의 시작지점을 0으로하여 16번 테케 오답,,,

javascript 구현 시 끝지점을 Math.max를 통해 [...diffs]를 하니,,, 15번부터 인가 쭉 오답,,,, Math.max에 들어가는 인자가 많아지면 런타임 에러가 발생한다고 한다,,, ㅜ