Daily LeetCode Challenge - 2448. Minimum Cost to Make Array Equal

Problem From.

https://leetcode.com/problems/minimum-cost-to-make-array-equal/

오늘 문제는 nums 와 cost 가 주어질때, nums 의 원소를 하나 바꾸는데 각각의 cost 의 index 에 대치되는 비용만큼 든다고 가정할때, nums 의 원소를 모두 같은 원소로 바꾸는 최소 비용을 구하는 문제였다.

이 문제는 볼록함수의 선형합은 볼록함수이다 라는 정의를 이용해서 풀 수 있었는데, 이를 이용하기 위해 이진탐색을 사용하였다. 먼저 nums 에서 최소값과 최대값을 찾아낸 다음, 각각 start 와 end 로 가정하여, 이진탐색을 시작한다.

start 에서 바꾸는 비용이 end 를 바꾸는 비용보다 크다면, start 를 mid 로 만들고, end 를 바꾸는 비용이 start 를 바꾸는 비용보다 크다면 end 를 start 로 만드는 식으로 반복하여, start 가 end 보다 커지는 지점을 찾아내어 그 값을 반환하면 최솟값을 구할 수 있었다.

class Solution {
    fun minCost(nums: IntArray, cost: IntArray): Long {
        var start = nums.min()!!
        var end = nums.max()!!

        var answer = Math.min(getCost(end, nums, cost), getCost(start, nums, cost))

        while (start < end) {
            val mid = start + (end - start) / 2
            val midCost = getCost(mid, nums, cost)

            answer = Math.min(answer, midCost)
            
            if (midCost < getCost(mid + 1, nums, cost)) {
                end = mid
            } else {
                start = mid + 1
            }

        }

        answer = Math.min(answer, getCost(start, nums, cost))

        return answer
    }
    
    private fun getCost(target: Int, nums: IntArray, cost: IntArray): Long {
        var temp = 0L

        for(i in nums.indices) {
            val num = nums[i].toLong()
            val changeCost = cost[i].toLong()
            temp += Math.abs(target - num) * changeCost
        }

        return temp
    }
}