Please enable JavaScript to view the comments powered by Disqus.347. Top K Frequent Elements 풀이, Bucket sort 를 사용하다
Search
🏢

347. Top K Frequent Elements 풀이, Bucket sort 를 사용하다

태그
Leetcode
Bucket Sort
Algorithm
공개여부
작성일자
2022/12/14
드디어 내 힘으로 풀었다. 핵심적으로 사용한 것은 Bucket sort 이다.
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
이 문제의 해결을 위한 constraints

Situation

주어진 배열 nums 의 숫자 중 많이 반복된 숫자 k개 까지를 반환하라.

Task

Bucket sort

[1, 1, 1, 2, 2, 3] 과 같이 숫자 배열이 주어졌다고 가정하면 오른쪽 표와 같은 hash table을 만들 수 있다.
사실 여기까지 만드는건 O(n)O(n) 이고 직관적으로 만들 수 있다.
key
value
1
3번
2
2번
3
1번
이제 자주 반복된 k 개를 어떻게 추출해야 할까? 이 부분이 문제이다.
여기서 사용한 개념이 bucket sort 이다.
이러한 배열을 통해서 sorting을 할 것인데
1은 3번 반복 되었고, 2는 2번, 1은 1번
이 그림과 같이 index 가 찾는 값이고, array 안에 반복 횟수가 들어간다면?
첫 번째 이유는 성립이 불가능하다. contraint 를 보면 array 안에 범위는 다음과 같다.
104<=nums[i]<=104-10^4 <= nums[i] <= 10^4
만약 -1000 이면 index를 -1000으로 만들어야 할까? 물론 이에 알맞게 array 의 규칙을 세울 수 있겠지만 부족한 알고리즘 풀이 시간에 알맞은 결정은 아니다.
두 번째 이유는 nums 안에 담긴 수 중에서 가장 큰 값이 1,000이면 array 의 length 는 10001 이 되어야 한다.
10000 이라는 숫자가 만약 4번 나왔다고 한다면?
물론 가능은 하지만, 효율적이진 않다.

Action

그렇다면 위의 첫 번째 이유를 해결하기 위해 반복 횟수를 index 로 두는 것이다.
nums = [1, 1, 1, 1, 1, 3, 3, 4] 와 같은 배열을 hash table 을 거쳐 bucket 에 담게 되면 다음과 같다.
위의 frequent 를 index 로, 각 frequent 에 해당하는 value 를 array 에 할당한다.
마지막으로 뒤에서 부터 배열을 순회하면서 k개 만큼 배열에 담아 반환하면 정렬이 되어있다.
이 그림에서 보면 nums.length 가 8이다. 그리고 배열은 최대 index가 8이다.
nums 의 길이가 8이지만, 8번 반복된 숫자가 있다면 n 은 반드시 1 이어야 한다.
8번이나 반복되어 index = 8 에 할당되기 위해선 n 이 1이어야 하기 때문이다.

Result

알고리즘 고수 분들은 코드가 짧던데 과연 성능이 어떠할까 걱정했지만 시간 복잡도, 공간 복잡도가 나쁘지 않다.
작성한 코드는 다음과 같다.
class Solution { public int[] topKFrequent(int[] nums, int k) { if (nums.length == 1 && k == 1) { return new int[] {nums[0]}; } int[] result = new int[k]; List<List<Integer>> bucket = new ArrayList<>(); for (int i = 0; i <= nums.length; i ++) { bucket.add(new ArrayList<>()); } Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i ++) { int cur = nums[i]; map.computeIfPresent(cur, (key, v) -> { v += 1; return v; }); map.putIfAbsent(cur, 1); } for (int value : map.keySet()) { int count = map.get(value); bucket.get(count).add(value); } int resultIndex = 0; int i = bucket.size(); while (resultIndex < k && i >= 0) { i -= 1; if (bucket.get(i).isEmpty()) { continue; } for (int j = 0; j < bucket.get(i).size(); j ++) { result[resultIndex] = bucket.get(i).get(j); resultIndex += 1; } } return result; } }
Java