[프로그래머스/Python] PCCP 기출문제 2번 / 퍼즐 게임 챌린지

 

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

프로그래머스

---

이 문제는 diff와 level을 비교해서 

level < diff일 경우와 level >= diff일 경우로 나눠서 진행합니다.

 

level < diff인 경우 (time_cur + time_prev) * (diff - level) + time_cur 만큼의 시간 소요

level >= diff인 경우 time_cur 만큼의 시간 소요

 

이 때 limit 시간 안에 해결할 수 있는 level을 찾으면 되는데요.

저는 처음에 반복문으로 1부터 max(diff)까지 순차적으로 확인했습니다.

 

방법1. 반복문 사용

def solution(diff, time, limit):
    m = max(diff)
    
    for level in range(1, m+1):
        answer = 0
        for i in range(len(time)):
            if level < diff[i]:
                answer += (time[i]+time[i-1])*(diff[i]-level) + time[i] 
            else:
                answer += time[i]
            if answer > limit:
                break
        if answer <= limit:
            return level

 

결과는 당연히 시간 초과로 실패였습니다.

 

 

어떤 방식을 써야할 지 고민하다가 for문으로 순차적 확인 대신 이진 탐색을 해야겠다는 생각을 했습니다.

 

방법2. 이진 탐색 사용

def bs(start, end, diff, time, limit):
    if start > end:
        return end+1
    level = (start+end)//2
    answer = 0
    for i in range(len(time)):
        if level < diff[i]:
            answer += (time[i]+time[i-1])*(diff[i]-level) + time[i] 
        else:
            answer += time[i]
    if answer <= limit:
        return bs(start, level-1, diff, time, limit) # level 최솟값을 찾기 위해 왼쪽으로
    else: 
    	# answer > limit
        return bs(level+1, end, diff, time, limit) # level을 더 증가시키기 위해 오른쪽으로
        
def solution(diff, time, limit):
    m = max(diff)
    res = bs(1, m, diff, time, limit)
    return res

 

tc 13이 5초가 넘게 걸렸는데, 이진 탐색으로 0.003초가 걸렸습니다.

이제 순차적으로 탐색하는 문제가 나오는데 숫자가 굉장히 많다면 이진 탐색을 사용하는 것으로!!