leetcode: 1217. Minimum Cost to Move Chips to The Same Position

문제링크

풀이1

• 모든 경우의 수를 전부 검사

import kotlin.math.abs
import kotlin.math.min

class Solution {
    fun minCostToMoveChips(positions: IntArray): Int {
        var minCost = Int.MAX_VALUE
        for (i in 0 until positions.size) {
            var cost = 0
            for (j in 0 until positions.size) {
                if (i != j) {
                    cost += (abs(positions[i] - positions[j]) % 2)
                }
            }
            minCost = min(minCost, cost)
        }
        return minCost
    }
}

시간복잡도 : O(N^2)
공간복잡도 : O(N)

풀이2

• 짝수끼리는 2씩 차이가 나므로 한 곳으로 모을 수 있고 홀수 역시 한 곳으로 모을 수 있다.
• 짝수가 모인 곳과 홀수가 모인 곳의 위치를 또 한 곳으로 모으려면 짝수 위치에 있는 chip을 홀수로 다 옮기거나 그 반대가 된다.
• 즉, 짝수의 총 개수와 홀수의 총 개수 중 작은 값이 minCost가 된다.

import kotlin.math.min
class Solution {

    fun minCostToMoveChips(positions: IntArray): Int {
        var oddCount = 0
        var evenCount = 0
        for (position in positions) {
            if (position and 1 == 1) oddCount++
            else evenCount++
        }
        return min(oddCount, evenCount)
    }
}

시간복잡도 : O(N)
공간복잡도 : O(N)