347. Top K Frequent Elements

#Algorithm #Algorithm-Divide_N_Conquer #Algorithm-Bucket_Sort

347. Top K Frequent Elements

1. 문제

1-1. 원문

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:
Input: nums = [1], k = 1
Output: [1]

Constraints:

1-2. 내용 번역

주어진 배열이 있을때, 배열 안의 숫자들의 출현빈도가 가장 높은 k개의 숫자를 리턴해라. 숫자의 출력 순서는 상관없다. (숫자 Set은 유일함을 보장한다.)

2. 문제 이해

2-1. 내용 이해

nums=[1,1,1,2,2,3], k=2 이면 nums 배열안의 숫자중에 출현 빈도가 가장 높은 2개의 수를 구하는 것이다. 1은 3번, 2는 2번, 3은 1번 나타나기 때문에 가장 많이 출현하는 수는 1, 그 다음은 2가 되어서 output은 [1, 2] 혹은 [2, 1]가 되는 것이다.

2-2. 접근법 생각

우선 어떤 수가 얼마나 나왔는지를 먼저 구해야겠네.
-> 그럼 루프 돌리면서 해시맵에다가 출현 빈도를 더해 나가야겠다.
...
그리고나서는.. 이 맵을 출현빈도대로 정렬해야겠는데..
-> sortedWith에 Comparable을 넣어서 정렬시켜버릴 수 있겠지만 이 정렬 알고리즘을 짜라는게 문제니까 이건 생략하자.
-> 그럼 해시맵을 array로 만들고 내가 아는 정렬 알고리즘을 사용해야겠네. 지금 익숙한건 머지소트랑 퀵소트니까 이걸 써봐야겠다. 으.. Int가 아니라 Pair를 가지고 정렬을 해야하니까 코드가 좀 복잡해지네..

2-3. 적용한 풀이

머지소트, 퀵소트

전체를 모두 정렬해야 한다. 의도하는 바를 구현하기에는 닭잡는데 소칼 쓰는 격이다.

Bucket Sort

추후에 여러 풀이를 보다가 이게 문제가 원하는 모범 솔루션인 것 같다는 생각이 들었다.

3. 구현

머지소트

class Solution {
    fun topKFrequent(nums: IntArray, k: Int): IntArray {
        val resultArr = IntArray(k)
        val countingMap = HashMap<Int, Int>()

        for (i in 0..nums.size-1) {
            val key = nums[i]
            val updatingCount = countingMap.getOrPut(key){0} + 1
            countingMap.put(key, updatingCount)
        }

        val targetArr: Array<Pair<Int, Int>> = Array<Pair<Int, Int>>(countingMap.size) { Pair(0,0) }
        var idx = 0

        for ((num, counting) in countingMap) {
            targetArr[idx++] = Pair<Int, Int>(counting, num)
        }

        val sortedArr = mergeSort(targetArr)

        for (i in 0..k-1) {
            resultArr[i] = sortedArr[i].second
        }

        return resultArr
    }

    fun mergeSort(targetArr: Array<Pair<Int,Int>>): Array<Pair<Int,Int>> {
        val targetArrSize = targetArr.size

        if (targetArrSize == 1) return arrayOf(Pair(targetArr[0].first, targetArr[0].second))

        val mid = targetArrSize/2
        val leftArr = mergeSort(targetArr.sliceArray(IntRange(0, mid-1)))
        val rightArr = mergeSort(targetArr.sliceArray(IntRange(mid, targetArrSize - 1)))

        var leftIdx = 0
        var rightIdx = 0
        var sortedIdx = 0

        val sortedArr: Array<Pair<Int, Int>> = Array<Pair<Int, Int>>(targetArrSize) { Pair(0,0) }

        while(leftIdx < leftArr.size && rightIdx < rightArr.size) {
            if (leftArr[leftIdx].first > rightArr[rightIdx].first) {
                sortedArr[sortedIdx++] = leftArr[leftIdx++]
            } else {
                sortedArr[sortedIdx++] = rightArr[rightIdx++]
            }
        }

        while(leftIdx < leftArr.size) {
            sortedArr[sortedIdx++] = leftArr[leftIdx++]
        }

        while(rightIdx < rightArr.size) {
            sortedArr[sortedIdx++] = rightArr[rightIdx++]
        }

        return sortedArr
    }
}

퀵소트

class Solution {
    fun topKFrequent(nums: IntArray, k: Int): IntArray {
        val countingMap = HashMap<Int, Int>()

        for(num in nums) {
            countingMap.put(num, countingMap.getOrPut(num){0}+1)
        }

        val countingValArr = IntArray(countingMap.size)
        var idx = 0

        for((key, counting) in countingMap) {
            countingValArr[idx++] = counting
        }

        val limitVal = quickSort(countingValArr)[k-1]
        val resultArr = IntArray(k)
        
        idx = 0
        for((key, counting) in countingMap) {
            if (counting >= limitVal) {
                resultArr[idx++] = key
            }
        }

        return resultArr
    }

    fun quickSort(countingArr: IntArray): IntArray {
        if (countingArr.size == 1) return countingArr

        val arrSize = countingArr.size
        val pivot = countingArr[arrSize-1]
        var leftIdx = 0
        var rightIdx = arrSize-2

        while(leftIdx < rightIdx) {
            while (countingArr[leftIdx] > pivot && leftIdx < rightIdx) {
                leftIdx++
            }

            while(countingArr[rightIdx] <= pivot && leftIdx < rightIdx) {
                rightIdx--
            }

            val temp = countingArr[rightIdx]
            countingArr[rightIdx] = countingArr[leftIdx]
            countingArr[leftIdx] = temp
        }

        if (countingArr[leftIdx] <= pivot) {
            countingArr[arrSize-1] = countingArr[leftIdx]
            countingArr[leftIdx] = pivot
        }
        
        if (arrSize-1 == leftIdx) {
            return quickSort(countingArr.sliceArray(IntRange(0, leftIdx)))
        }

        return quickSort(countingArr.sliceArray(IntRange(0, leftIdx))) + quickSort(countingArr.sliceArray(IntRange(leftIdx+1, arrSize-1)))
    }

}

버켓소트

class Solution {
    fun topKFrequent(nums: IntArray, k: Int): IntArray {
        val countingMap = HashMap<Int, Int>()

        for(num in nums) {
            countingMap.put(num, countingMap.getOrPut(num){0}+1)
        }

        val bucket = Array<ArrayList<Int>>(nums.size+1){ArrayList<Int>()}

        for((key, counting) in countingMap) {
            bucket[counting].add(key)
        }

        val resultArr = IntArray(k)
        var count = 0

        for(idx in nums.size downTo 0) {
            if(bucket[idx].size > 0) {
                for(bucketNum in bucket[idx]) {
                    resultArr[count++] = bucketNum
                }
            }

            if (count == k) break
        }

        return resultArr
    }
}

4. 복잡도

머지소트

퀵소트

버켓소트