[Leetcode] 347번 - Top K Frequent Elements (using Array)

1. 문제 파악

• 문제 링크: https://leetcode.com/problems/top-k-frequent-elements/
• 문제: 주어진 배열의 요소값중에서 빈도수가 가장 높은 요소를 k개 저장한 배열을 반환해라.
• 시간복잡도 파악: 입력크기가 100000이라서 O(N\logN) 이내어야한다.
• 문제 나눠서 정의
  1. 배열을 순차적으로 조회하면서 요소별로 빈도수 연산 -> 가장 빈도수가 큰 요소들을 반환해야하므로 동적으로 빈도수 연산을 하지못한다. 따라서 각 요소별로 모든 빈도수를 계산하고 key, value를 상요하는 자료구조에 저장해야한다.
  2. 자료구조를 빈도수 크기로 정렬한다. (단, 빈도수가 중복되는 요소값이 존재한다.)
  3. 정렬된 자료구조에서 k개 만큼 값을 가져와서 반환 배열에 저장

 

2. 핵심 문제 풀이 도출

1. 배열을 순회할때 각 요소별로 모든 빈도수를 계산하고, HashMap에 요소값을 key로 하고 빈도수는 value로 저장한다. -> 평균 O(n)
2. 자료구조를 빈도수 크기로 정렬하는 방법에는 다음 2가지 방법이 있다.
   • HashMap에서 Map.Entry를 가져와서 key와 value 쌍을 리스트에 저장한다. 리스트에서 entry의 value를 기준으로 내림차순 정렬을 한다. -> 평균 O(nlogn)
   • 빈도수를 인덱스로하는 리스트 배열을 생성하고 저장하면 오름차순 정렬된 것이다. -> O(n)
3. 정렬된 자료구조에서 k개 만큼 값을 가져와서 반환 배열에 저장후 반환: -> O(k)

1, 2, 3번 로직은 각각 실행된다. 2번 로직에서 정렬 알고리즘을 쓰면 평균 O(nlogn)이지만, 빈도수를 인덱스로하는 리스트 배열에 저장하면 O(n)내에 끝낼수있다. 따라서 이 문제는 최대 평균 O(n) 내에 처리할수 있다.

 

3. 입출력 케이스 도출

 

위의 알고리즘대로라면 엣지 케이스까지 커버가능하다.

• 일반 케이스
  • nums = [1,1,1,2,2,3], k = 2 -> [1,2]
  • nums = [1], k = 1 -> [1]
• 엣지 케이스
  • [1,1,1,2,2,2,3], k = 2 -> [1, 2]

 

4. 코드로 문제 풀이 구현

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int n = nums.length;
        // 1. 배열 요소에 대한 빈도수 저장
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int num: nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); // default 0
        }

        // 2. 자료구조를 빈도수 크기로 정렬
        List<Integer>[] freqList = new ArrayList[n + 1]; // n개 까지 빈도수 가능하므로 하나더 크게 생성
        // 해시맵에서 키와 값을 둘다 가져와야한다.
        // 키를 먼저 가져와서 키로 값을 가져온다.
        for (int freqKey: freqMap.keySet()) {
            int freqValue = freqMap.get(freqKey);
            if (freqList[freqValue] == null) { 
                freqList[freqValue] = new ArrayList<>(); // 저장할 리스트 초기화
            }
            freqList[freqValue].add(freqKey);
        }

        // 3.  정렬된 자료구조에서 k개 만큼 값을 가져와서 반환 배열에 저장후 반환 (빈도수가 가장 높은 뒤에서부터 조회하며 반환할 결과값 저장)
        List<Integer> result = new ArrayList<>();
        for (int i = freqList.length - 1; i >= 0 && result.size() < k; i--) {
            if (freqList[i] != null) {
                result.addAll(freqList[i]);
            }
        }
        return result.stream().mapToInt(i -> i).limit(k).toArray(); 
    }
}