[Kotlin] programmers 퍼즐 게임 챌린지

출처

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

프로그래머스

 

 

풀이

첫 시도

class Solution {
    fun isComplicated(time_prev : Int, time_cur : Int, diff : Int, level : Int) : Int{
        return (time_cur+time_prev)*(diff-level) + time_cur
    }
    fun solution(diffs: IntArray, times: IntArray, limit: Long): Int {
        var minLevel: Int = 1
        while(true) {
            var totalTime = 0L
            for (i in 0 until diffs.size) {
                if (minLevel >= diffs[i]) {
                    totalTime += times[i]
                }   
                else {
                    totalTime += isComplicated(times[i-1], times[i], diffs[i], minLevel)
                }
                if(totalTime > limit) break;
            }
            if(totalTime <= limit) {
                break;
            }
            minLevel += 1
        }
        return minLevel
    }
}

 

변수의 범위가 넓기 때문에 시간 초과가 발생했다. 적합한 값을 1부터 찾는 것이 아니라, 다른 방법으로 적합한 값을 찾아야 한다.

 

두번째 시도

class Solution {
    fun isComplicated(time_prev: Int, time_cur: Int, diff: Int, level: Int): Int {
        return (time_cur + time_prev) * (diff - level) + time_cur
    }
    fun calculateTotalTime(diffs: IntArray, times: IntArray, limit: Long, minLevel: Int): Long {
        var totalTime = 0L
        for (i in diffs.indices) {
            if (minLevel >= diffs[i]) {
                totalTime += times[i]
            } else {
                totalTime += isComplicated(times.getOrElse(i - 1) { 0 }, times[i], diffs[i], minLevel)
            }
            if (totalTime > limit) {
                return totalTime
            }
        }
        return totalTime
    }

    fun solution(diffs: IntArray, times: IntArray, limit: Long): Int {
        var low = 1
        var high = diffs.maxOrNull()?:100000  // diffs[i]는 최대 100,000
        while (low <= high) {
            val mid = (low + high) / 2
            val totalTime = calculateTotalTime(diffs, times, limit, mid)
            if (totalTime > limit) {
                low = mid + 1
            } else {
                high = mid - 1
            }
        }

        return low
    }
}

이진탐색으로 풀이.

최소가 나오면 완탐으로 풀려하는 습관을 고쳐야겠다.