eetcode - reduce array size to the half(kotlin)

5732 단어 leetcodekotlinkotlin

level - medium

[문제 내용]
배열 중에 삭제할 숫자 집합을 골라 원래보다 절반이하로 삭제하는 set의 최소 크기를 반환

[example 1]

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array.

[example 2]

Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: The only possible set you can choose is {7}. This will make the new array empty.

[example 3]

Input: arr = [1,9]
Output: 1

[example 4]

Input: arr = [1000,1000,3,7]
Output: 1

[example 5]

Input: arr = [1,2,3,4,5,6,7,8,9,10]
Output: 5

[해결방법]
주어진 배열의 중복인자들의 개수를 구해 map에 저장한다.
중복된 개수에 대해 내림차순으로 정렬한후,
내림차순으로 주어진 배열에서 하나씩 없애 꺼낸 개수가 절반 이상일때
뺀 숫자들의 개수를 반환한다.

class Solution {
    fun minSetSize(arr: IntArray): Int {
        val counts = HashMap<Int, Int>()
        // 중복된 숫자 count
        for(a in arr) {
            counts[a] = counts.getOrDefault(a, 0) + 1
        }

        // 중복된 개수에 대해 내림차순 정렬
        val keySet = counts.keys.toList()
        Collections.sort(keySet, kotlin.Comparator { t, t2 -> counts[t2]!!.compareTo(counts[t]!!) })
        
        val half = arr.size/2
        var count = 0
        var value = 0
        // 중복 개수의 내림차순으로 숫자 꺼냄
        for(key in keySet) {
            count++
            value += counts[key]!!
            // 꺼낸 개수가 절반보다 크거나 같을경우 break
            if(half <= value) {
                break
            }
        }

        return count
    }
}

좋은 웹페이지 즐겨찾기