.leetcode(347. Top K Frequent Elements)

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

 

2. 2022.04.08 시도

소요시간: 7분

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        
        for (int i=0; i<nums.length; i++) {
            countMap.put(nums[i], countMap.getOrDefault(nums[i], 0)+1);
        }
        
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(countMap.entrySet());
        Collections.sort(list, (o1, o2) -> {
            return o1.getValue().compareTo(o2.getValue()) * -1; 
        });
        
        int counter=0;
        int[] ret = new int[k];
        for (Map.Entry<Integer, Integer> each: list) {
            ret[counter++] = each.getKey();
            if (counter == k) {
                break;
            }
        }
        
        return ret;
    }
}

풀이 접근 과정

map을 이용해서 풀었다.

 

느낀점

• 지금 보니, 1년전하고 똑같이 푼거나 다름없다. 다만 조금 더 간단한 코드를 짰다.
• Heap(PriorityQueue)를 사용해서 다시 풀었다. 낯설다. 우선순위 큐를 이용해 작은 것을 앞에 배치한다. 그리고 특정 사이즈를 넘어가면 poll을 통해 내보낸다. 그러면 자동으로 큰거 두개가 남게 된다.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        
        for (int i=0; i<nums.length; i++) {
            countMap.put(nums[i], countMap.getOrDefault(nums[i], 0)+1);
        }
        
        
        
        PriorityQueue<Integer> pq = new PriorityQueue((o1, o2) -> {
            return countMap.get(o1).compareTo(countMap.get(o2)); 
        });
        
        
        for (int key: countMap.keySet()) {
            pq.add(key);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        int counter=0;
        int[] ret = new int[k];
        while (!pq.isEmpty()) {
            ret[counter++] = pq.poll();
        }
        
        return ret;
    }
}

• merge sort(divide and conquer)
  • 기존 다른 문제에서는 node를 이용해서 merge sort를 완성했는데, 원리만 따와서 배열로 만들어보았다. 공간의 낭비가 아무래도 있는 것같다. 하지만 분할정복의 원리면만 보면 좋겠다.
  • https://velog.io/@claude_ssim/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-Merge-Sort

// merge sort
class Solution {
    Map<Integer, Integer> countMap = null;
    public int[] topKFrequent(int[] nums, int k) {
        countMap = new HashMap<>();
        
        for (Integer each: nums) {
            countMap.put(each, countMap.getOrDefault(each, 0)+1);
        }
        
        int index = 0;
        int[] unique = new int[countMap.size()];
        for(int each: countMap.keySet()) {
            unique[index++] = each;
        }
        
        
        int[] sorted = dq(unique, 0, unique.length-1);
        
        int[] ret = new int[k];
        for (int i=0; i<k; i++) {
            ret[i] = sorted[i];
        }
        
        return ret;
    }
    
    private int[] dq(int[] unique, int p, int q) {
        if (p>=q) {
            return new int[]{unique[p]};
        }
        int mid = p + (q-p)/2;
        int[] left = dq(unique, p, mid);
        int[] right = dq(unique, mid+1, q);
        return merge(left, right);
    }
    
    private int[] merge(int[] left, int[] right) {
        int leftIndex = 0;
        int rightIndex = 0;
        
        int counter=0;
        int[] merged = new int[left.length+right.length];
        while(leftIndex < left.length && rightIndex < right.length) {
            if (countMap.get(left[leftIndex]) < countMap.get(right[rightIndex])) {
                merged[counter++] = right[rightIndex];
                rightIndex++;
            } else {
                merged[counter++] = left[leftIndex];
                leftIndex++;
            }
        }
        if (left.length == leftIndex) {
            for(int i=rightIndex; i<right.length; i++) {
                merged[counter++] = right[i];
            }
        } else if (right.length == rightIndex) {
            for(int i=leftIndex; i<left.length; i++) {
                merged[counter++] = left[i];
            }
        }
        
        return merged;
    }
    
}

• quick sort(Hoare's selection algorithm)을 이용하여 풀었다. 솔루션을 보고 풀었다.

// quick sort(Hoare's selection algorithm)
class Solution {
    int[] unique;
    Map<Integer, Integer> countMap = null;
    public int[] topKFrequent(int[] nums, int k) {
        countMap = new HashMap<>();
        
        for (Integer each: nums) {
            countMap.put(each, countMap.getOrDefault(each, 0)+1);
        }
        
        int index = 0;
        unique = new int[countMap.size()];
        for(int each: countMap.keySet()) {
            unique[index++] = each;
        }
        
        int n = unique.length;
        quicksort(0, n-1, n-k);
        
        return Arrays.copyOfRange(unique, n-k, n);
    }
    
    private void quicksort(int s, int e, int k) {
        if (s == e) return;
        
        Random randomNumber = new Random();
        int pivot = s + randomNumber.nextInt(e-s);
        
        pivot = partition(s, e, pivot);
        
        if (pivot == k) {
            return;
        } else if (pivot > k) {
            quicksort(s, pivot-1, k);
        } else {
            quicksort(pivot+1, e, k);
        }        
    }
    
    private int partition(int left, int right, int pivot_index) {
        int pivotCount = countMap.get(unique[pivot_index]);

        swap(pivot_index, right);
        int store_index = left;
        
        for (int i=left; i<right; i++) {
            if (countMap.get(unique[i]) < pivotCount) {
                swap(store_index, i);
                store_index++;
            }
        }
        
        swap(store_index, right);
        
        return store_index;
    }
    
    
    private void swap(int p, int q) {
        int temp = unique[p];
        unique[p] = unique[q];
        unique[q] = temp;
    }
    
}

---

 

1. 2021.01.16 시도

소요시간: 9분

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        Map<Integer, Integer> counter = new HashMap<>();
        for(int i=0; i<nums.length; i++) {
            if (counter.containsKey(nums[i])) {
                counter.put(nums[i], counter.get(nums[i]) +1);
            } else {
                counter.put(nums[i], 1);
            }
        }

        for (int i=0; i<k; i++) {
            int max = 0;
            int maxValue = 0;
            for(Map.Entry<Integer, Integer> each: counter.entrySet()) {
                if (maxValue < each.getValue()) {
                    maxValue = each.getValue();
                    max = each.getKey();
                }    
            }

            counter.remove(max);
            result[i] = max;
        }

        return result;
    }
}

풀이 접근 과정

map에 담고 그다음에 가장 큰 value를 순서대로 구하면 되겠다.

 

느낀점

• 지금 푼 풀이는 실제로 통과하긴했지만 시간은 nLogN에 들어오지 않는다.
• heap을 사용해서 풀어보자. heap은 PriorityQueue를 이용해서 풀 수 있다.
• quick sort에 대해서 배울 수 있는 기회였다. Lomuto's Partition와 Hoare's Partition 에 대해서 나온다. 파트셔닝을 어떻게 할지에 대한 것인데 결과적으로 Hoare's가 좋다. 왜냐면 문제에서는 유니크한 숫자일 수 밖에 없지만 정렬시 중복 숫자가 나올때도 Hoare로는 정렬이 가능하다고 한다. 반면에 Lomuto's는 안된다.
• quick정렬은 기본적으로 pivot이라고 랜덤하게 하나를 고르고, 그걸 기준으로 작은것은 왼쪽, 큰것은 오른쪽으로 나누는 것(파티셔닝)을 한다.
• Lomoto는 간단하다. 젤 오른쪽 것을 pivot으로 정하고 그걸 기준으로 적절한 swap을 통해 파티셔닝을 한다. 그리고 마지막에 가운데로 다시 쏙 돌아온다.
• Hoare도 간단하다. left, right의 가운데 점을 pivot으로 정하고 적절한 swap을 통해 파티셔닝하는 방법이다.

#heap
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        Map<Integer, Integer> counter = new HashMap<>();
        for(int i=0; i<nums.length; i++) {
            if (counter.containsKey(nums[i])) {
                counter.put(nums[i], counter.get(nums[i]) +1);
            } else {
                counter.put(nums[i], 1);
            }
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> counter.get(a) - counter.get(b));

        for(Integer key: counter.keySet()) {
            pq.add(key);
            if (pq.size() > k) pq.poll();
        }

        for (int i=k-1; i>=0; i--) {
            result[i] = pq.poll();
        }

        return result;
    }
}

 

참고

• heap에 대한 이해: https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
• 파티셔닝: pivot을 중심으로 왼쪽은 pivot보다 작은 것, pivot보다 큰 것은 오른쪽으로 이동
  • quick sort 설명: https://www.youtube.com/watch?v=MkPPFQgYABc
  • divide and conquer

 

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형