[프로그래머스] Lv. 2 - 퍼즐 게임 챌린지

제목: Lv. 2 - 퍼즐 게임 챌린지

시간: 1시간

 

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

프로그래머스

 

이 문제는 일반적인 구현 문제였다.

 

입출력 예시를 봤을 때 데이터가 꽤 큰걸 알고 있었지만, 일단 구현을 코딩을 했다.

 

첫 번째 풀이

import Foundation

// 난이도, 현재 소요시간, 이전 소요시간, 숙련도
// 문제 이해하는데 5분
func solution(_ diffs:[Int], _ times:[Int], _ limit:Int64) -> Int {
    var level = diffs.max()! // 모든 문제를 2분 안에 풀수 있는 최소값
    var resultLevel = level
    
    // 레벨이 1이상일 때만 반복
    while (level > 0) {
        var time = 0
        
        for i in (0 ..< diffs.count) {
            if diffs[i] <= level {
                time += times[i]
            } else {
                time += (diffs[i] - level) * (times[i] + times[i-1])
                time += times[i]
            }
        }
 
        if level < resultLevel && time <= limit {
            resultLevel = level
        }
 
        level -= 1
    }
    
    return resultLevel
}

 

다 하고 나니 일부 테스트 케이스에서 시간초과가 발견했고, 수정을 했다.

 

모든 것을 탐색하는 O(n)이 아닌 더 짧은 걸 해야했는데, 이진탐색이 적당해보였다.

 

두 번째 풀이

import Foundation

// 난이도, 현재 소요시간, 이전 소요시간, 숙련도
// 문제 이해하는데 5분
func solution(_ diffs:[Int], _ times:[Int], _ limit:Int64) -> Int {
    var l = 1
    var r = diffs.max()!
    var result = r
    
    while (l <= r) {
        var m = (l + r) / 2
        
        var time = 0
        
        for i in (0 ..< diffs.count) {
            if diffs[i] <= m {
                time += times[i]
            } else {
                time += (diffㅁs[i] - m) * (times[i] + times[i-1])
                time += times[i]
            }
        }
 
        if time > limit {
            l = m + 1
        } else {
            r = m - 1
            result = m  
            
        }
    }
    
    return result
}

 

다음엔 문제와 입출력 예시를 보고 시간초과가 날거같으면 미리 작업을 해보는게 좋을 것 같다.