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

1. 문제 링크

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

프로그래머스

 

2. 생각하기

- 문제가 길어서 이해하는데 좀 걸렸지만 문제 자체는 어렵지 않은데? 하며 호기롭게 While 문과 For 문을 함께 사용해서 도전. 오랜만에 문제 풀어서 시간초과를 간과했다...

- 이분탐색으로 구현하자는 아이디어까진 냈으나 구현에서 막혀버리고 설마 진짜 이분탐색이겠어 하며 다른 사람의 풀이를 참고함

- 이분탐색으로 푸는 게 맞았다. 다음에는 좀더 구현하려고 노력한 다음에 풀이를 보도록 하자!

 

3. 구현

- 정답코드 (이분탐색)

1) 현재 레벨에서의 최종 시간과 limit 시간을 비교해주는 함수 작성

2) start = 1, end = max(diffs) 에서 시작해 mid 값 갱신 

def solution(diffs, times, limit):
    def calculate_time(level):
        time = 0
        for i in range(len(diffs)) :
            if level >= diffs[i] :
                time += times[i]
            else :
                time += (diffs[i]-level)*(times[i-1]+times[i]) + times[i]
            
            if time > limit :
            	# 시간이 오버되면 바로 break
                break
        return time <= limit
    
    answer = 1
    start = 1
    end = max(diffs)
    
    while start <= end :
        mid = (start + end) // 2
        
        if calculate_time(mid) :
            answer = mid
            end = mid - 1
        else : 
            start = mid + 1

    return answer

 

- 오답:시간초과 (반복문)

def solution(diffs, times, limit):
    # diff : 현재 퍼즐 난이도
    # limit : 전체 제한시간
    # 구해야 할 것 : 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값 (모두 양의 정수)
    level = 0
    total_time = 10**15
    while limit < total_time :
        level += 1
        total_time = 0
        # total_time이 limit 보다 작아지면 종료
        for i in range(len(diffs)) :
            if level >= diffs[i]:
                total_time += times[i] # diffs[0] = 1 로 고정됨
            else :
                time_prev = times[i-1] # 이전 소요시간
                time_cur = times[i] # 현재 소요시간
                total_time += (diffs[i]-level)*(time_prev + time_cur)+time_cur
                if total_time > limit :
                	break
    return level