[LeetCode] 1300. Sum of Mutated Array Closest to Target(Kotlin)

0

LeetCode

목록 보기
45/58
post-thumbnail
post-custom-banner

[LeetCode] 1300. Sum of Mutated Array Closest to Target(Kotlin)

풀이

  • 이분 탐색 문제
  • 주의해야 할 테스트 케이스
input: 
arr = [15, 1,1,1,1,1,1,1,1,1,1,1], target = 50
answer: 15
import kotlin.math.*

class Solution {

    fun findBestValue(arr: IntArray, target: Int): Int {
        var minAbsDifference = Int.MAX_VALUE
        var optValue: Int? = null

        // binary search
        var left:Int  = 0
        var right: Int = arr.max() + 1
        var mid: Int? = null
        while(left < right){
            mid = (left + right)/2
            val difference:Long = target - getSum(mid!!, arr)
            if(difference > 0) left = mid!! + 1
            else right = mid!!

            val absDifference = abs(difference).toInt()
            if(minAbsDifference > absDifference){
                minAbsDifference = absDifference
                optValue = mid
            }
            else if(minAbsDifference == absDifference){
                if(optValue == null) optValue = mid
                else optValue = min(optValue, mid)
            }
        }
        return optValue ?: 0
    }
    
    private fun getSum(value: Int, arr: IntArray): Long = 
        arr.map{ it ->
            (if(it > value) value else it).toLong()
        }.sum()
}
profile
Be able to be vulnerable, in search of truth
post-custom-banner

0개의 댓글