eetcode - reduce array size to the half(kotlin)
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
}
}
Author And Source
이 문제에 관하여(eetcode - reduce array size to the half(kotlin)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mdok1112/leetcode-reduce-array-size-to-the-halfkotlin저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)