TIL #46

귤 고르기

한박스에 k개씩 귤을 담는데 배열이 크기별 개수가 주어질때 가장 적은 종류로 한박스에 k개를 담는 수를 반환해야 한다.

처음에 각 숫자가 몇개있는지 배열을 만들어 넣어준다. 해당 배열의 max의 값을 구해서 k에서 max를 빼주고 카운트하고 k가 0보다 작아질때 max를 몇 번 빼주었는지 반환하는 방법으로 풀었는데 몇몇 테스트케이스에서 시간초과가 문제였다.
그래서 다른사람의 힌트를 보고 배열을 내림차순으로 정렬해준 후 큰 수부터 가져와 변수에 더할때 마다 카운트하고 k보다 커졌을때 몇번더했는지 카운트 해줘서 해결했다.

---

나의풀이

class Solution {
    fun solution(k: Int, tangerine: IntArray): Int {
        var answer: Int = 0
        var size = tangerine.maxOrNull() ?: 0
        var cntArr = IntArray(size+1)
        for (i in tangerine){
            cntArr[i]++
        }
        
            var cnt = k
            while(cnt > 0){
                var max = cntArr.maxOrNull()
                
                if(max != null){
                    var maxIndex = cntArr.indexOf(max)
                    
                    cnt -= cntArr[maxIndex]
                    cntArr[maxIndex] = 0
                    answer++
                } else{
                    return 0
                }
            }
            
        return answer
    }
}

시간초과 발생

class Solution {
    fun solution(k: Int, tangerine: IntArray): Int {
        var answer: Int = 0
        var size = tangerine.maxOrNull() ?: 0
        var cntArr = IntArray(size+1)
        for (i in tangerine){
            cntArr[i]++
        }
        cntArr.sortDescending()
        var cnt = 0
        for(i in cntArr){
            cnt += i
            answer++
            if(cnt >= k){
                break
            }
        }
        
            
        return answer
    }
}

---

다른사람의 풀이

class Solution {
    fun solution(k: Int, tangerine: IntArray): Int {
        var answer: Int = 0
        var limit = 0
        tangerine.groupBy { it }.toList().sortedByDescending { it.second.size }.forEach{
        if(limit >= k){
            return answer
        }
        limit += it.second.size
        answer++
    }

    return answer
    }
}