[프로그래머스/Swift] 340212번 - 퍼즐 게임 챌린지

🔗 문제 링크

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

💡 구현 아이디어

1. 레벨은 1~max(diffs) 의 숫자중 하나
2. 레벨을 1부터 전부 비교할 수는 없으니 이분탐색으로 범위를 줄여나감

💻 코드

import Foundation

func solution(_ diffs:[Int], _ times:[Int], _ limit:Int64) -> Int {
    let diffs: [Int64] = diffs.map { Int64($0) }
    let times: [Int64] = times.map { Int64($0) }
    
    var low: Int64 = 1
    var high: Int64 = -1
    var mid: Int64 = -1
    
    for diff in diffs { high = max(high, diff) }
  
    while low <= high {
        mid = (low + high) / 2
        let result = checkLevel(diffs, times, mid)
        if result <= limit {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return Int(low)
}

func checkLevel(_ diffs:[Int64], _ times:[Int64], _ level: Int64) -> Int64 {
    var result: Int64 = 0
    var time_prev: Int64 = 0 
    
    for (diff, time) in zip(diffs, times) {
        if diff <= level {
            result += time
        } else {
            result += (diff - level) * (time + time_prev) + time
        }
        time_prev = time
    }
    return result
}

❌ 틀린 이유 및 틀린 부분

결과값 반환에서 return Int(mid)로 해서 틀림 → low 값을 반환해야함

⏳ 시간 복잡도

O(log N) * O(N) = 레벨 접근 횟수 * 각 레벨당 diffs, times 접근 횟수

📌 풀이 또는 기억할 정보

문제가 어려워질수록 이분탐색은 기본적인 소양이된다.

값의 범위가 커지면 이분탐색을 떠올리자