[자바 알고리즘 인터뷰] ch 11. 해시 테이블 (4) 상위 k빈도 엘리먼트

https://leetcode.com/problems/top-k-frequent-elements/description/

 

- 빈도순으로 k개의 엘리먼트를 추출하라 

 

 

풀이 1) 빈도수를 저장하고 빈도순으로 엘리먼트 추출 

 

- 각 엘리먼트의 빈도를 추출하고 이를 빈도순으로 저장하거나 정렬한 다음, k번만큼 추출하면 문제를 풀이할 수 있다 .

 

- 각 엘리먼트의 빈도 추출

- 입력값 nums를 반복하며 빈도수를 저장할 해시맵 frequencyMap을 선언하고 여기에 빈도를 저장한다. 

- 처음 빈도를 계산한다면 0으로, 기존에 값이 있다면 그 값을 가져오고 모두 +1을 한다. 

 

//각 엘리먼트의 빈도수를 저장할 해시맵 선언, 엘리먼트=> 빈도수
Map<Integer,Integer> frequencyMap = new HashMap<>();
//각 엘리먼트의 빈도수를 반복하며 계산하여 저장
for(int n : nums)
{
    //처음 빈도수를 계산하는 엘리먼트는 기본값 0으로, 모두 +1하여 저장
    frequencyMap.put(n,frequencyMap.getOrDefault(n,0)+1);
}

 

 

frequencyMap
{
    1=3,
    2-2,
    3=1,
    4=1,
}

 

 

- 두 번째 과정으로 빈도를 저장하여 상위 빈도를 찾는 과정 

- buckets라는 해시맵을 선언하고 여기에 키는 빈도수, 값은 엘리먼트로 한다. 

- 여기서 엘리먼트는 여러가지가 될 수 있다. 같은 빈도 엘리먼트가 여러 개 될 수 있기 때문이다. 

- 따라서 값을 List로 처리하여 Map<Integer, List<Integer>>로 선언한다. 

 

//빈도수 기준으로 각 엘리먼트를 저장할 해시맵 선언, 빈도수=>엘리먼트
Map<Integer, List<Integer>>buckets = new HashMap<>();
//각 엘리먼트를 반복하며 이번에는 빈도수를 키로, 엘리먼트를 값으로 저장 
for(int elem : frequencyMap.keySet()) {
    int frequency = frequencyMap.get(elem);
    //빈도수에 해당하는 엘리먼트가 존재하지 않으면 빈 리스트 생성
    List<Integer>elems = buckets.getOrDefault(frequency, new ArrayList<>());
    //저장할 값에 엘리먼트 추가
    elems.add(elem);
    //빈도수를 키로, 엘리먼트를 값으로 저장
    buckets.put(frequency, elems);
}

 

 

{
    3=[1],
    2=[2],
    1=[3,4]
}

 

 

- 결과 변수 result를 선언하고 여기에 전체 엘리먼트의 개수부터 하나씩 줄여가며 해당하는 엘리먼트를 결과에 삽입한다. 

- 이렇게 k번까지 추출하면 빈도수가 높은 순으로 k번만큼의 결과를 추출할 수 있다. 

 

//결과로 리턴할 변수 선언, k번까지만 추출하면 되므로 k만큼 선언
int result[] = new int[k];
int idx = 0;
//전체 엘리먼트 수에서 하나씩 내려가며 해당하는 빈도의 엘리먼트 추출
for(int fq = nums.length; fq>=0&& idx<k; fq--)
{
    //해당 빈도에 값이 존재한다면 엘리먼트를 결과 변수에 삽입
    if(buckets.get(fq)!=null)
    {
        //해당 빈도에 여러 엘리먼트가 있을 수 있으므로 반복하여 모두 삽입
        for(int elem : buckets.get(fq))
        {
            result[idx] = elem;
            idx++;
        }
    }
}
return result;

12밀리초 

 

 

풀이 2) 우선순위 큐를 이용한 풀이 

 

- 우선순위 큐에 삽입한 다음, 빈도순으로 k번 추출하면 동일한 결과를 얻을 수 있다. 

- 각 엘리먼트를 저장하는 대신, 우선순위 큐에 엘리먼트와 빈도수를 삽입 

 

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //각 엘리먼트의 빈도수를 저장할 해시맵 선언, 엘리먼트=> 빈도수
        Map<Integer,Integer> frequencyMap = new HashMap<>();
        //각 엘리먼트의 빈도수를 반복하며 계산하여 저장
        for(int n : nums)
        {
            //처음 빈도수를 계산하는 엘리먼트는 기본값 0으로, 모두 +1하여 저장
            frequencyMap.put(n,frequencyMap.getOrDefault(n,0)+1);
        }

        //빈도순으로 정렬되는 우선순위 큐 선언
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> b[1]-a[1]);
        //우선순위 큐에 각 엘리먼트와 빈도수 삽입
        for(int elem : frequencyMap.keySet())
        {
            pq.add(new int[]{elem, frequencyMap.get(elem)});
        }

        //결과로 리턴할 변수 선언
        int result[] = new int[k];
        //k번까지만 반복하여 우선순위 큐에서 결과 추출
        for(int i=0; i<k; i++)
        {
            result[i] = pq.poll()[0];
        }
        return result;
    }
}

13밀리초