LeetCode # 347. HashMap과 PriorityQueue, Stream을 이용해 풀어보자

문제. <347. 상위 k 빈도 엘리먼트(Top K Frequent Elements)>

내용: 빈도순으로 k개의 엘리먼트를 추출하라.

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 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
`k` is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

---

내용 해석

1) 정수형 배열 nums와 추출할 갯수 k를 입력받는다.

2) nums의 요소별 빈도를 확인하여 빈도순으로 k개 추출 후 해당 요소를 정수형 배열로 반환한다.

3) 정수형 배열 nums는 최대 길이 10^5, 배열의 요소 nums[i]의 범위는 -10^5 ~ 10^5 이다.

풀이 1. HashMap과 Stream 사용

- 시간복잡도: O(n log n), LeetCode 17초

내용을 확인 후, Map을 이용해 요소와 빈도 수를 저장하고, k개 만큼 정렬된 값을 반환하면 되겠다는 생각이었다.

다만, HashMap으로 저장한 값들을 어떻게 정렬할 것인가? 라는 고민이 생겼고, Stream API를 통해 해결했다.

public int[] topKFrequent_17(int[] nums, int k) { // O(n log n)
        // 1. 배열의 요소와 빈도 수를 HashMap에 저장
        // 2. Stream API를 사용해 1) value 기준 정렬 2) key값만 추출 3) k 갯수만큼 추출 4) int형 배열로 반환

        // 1
        Map<Integer, Integer> elements = new HashMap<>();
        for (int i : nums) {
//            elements.put(i, elements.containsKey(i) ? elements.get(i) + 1 : 1); // 3항 연산자 사용
            elements.put(i, elements.getOrDefault(i, 0) + 1); // getOrDefault 사용
        }

        // 2
        return elements.entrySet()                                  // Set<Map.Entry<K,V>> 형태로 변경
                .stream()                                           // 데이터 요소를 다루기 위한 Stream 객체로 변환
                .sorted((o1, o2) -> o2.getValue() - o1.getValue())  // value 값으로 내림차순 정렬 (o2.getValue().compareTo(o1.getValue())
                .limit(k)                                           // k개 만큼 갯수 제한
                .mapToInt(Map.Entry::getKey)                        // map() => toArray 시 Object[] or Integer[]로 반환됨
                .toArray();
    }

1) 향상된 for문을 사용해 Map  타입 변수 'elements'에 값을 저장할 때, 처음에 삼항 연산자를 사용했다가, getOrDefault()로 변경했다.

삼항연산자는 containsKey() 메서드를 호출 후 값을 가져오는 경우 get()까지 수행하기에, 한 번의 호출로 수행되는 getOrDefault()보다 수행 횟수는 더 많다고 볼 수 있다.

해시 테이블의 조회는 매우 빠르기에 두 코드의 성능 차이는 미미하지만, 성능 최적화와 가독성을 위해 getOrDefault()메서드로 변경하였다.

 

2) Stream을 사용하면서 신경썼던 부분은 ☝내림차순 정렬, ✌int[]배열로 반환, 두 가지였다.

☝ Stream에서는 srorted() 메서드를 제공하는데, 다루는 데이터의 요소가 Comparable의 구현했을 경우 기분 순서로 동작한다. 하지만 현재 다루고 있는 데이터인 Map.Entry<K,V>는 HashMap에서 Comparable을 구현하지 않았다. 그렇기에 value값을 내림차순으로 정렬하도록 구현했다.

✌ Stream의 종료 연산으로 toArray()를 사용하면 배열로 반환할 수 있다. 문제에서는 int 배열로 반환하도록 되어 있다.

처음 구현할 때 map() 중간 연산으로 현재의 Map.Entry<K,V> 구조가 아닌 Key값인 Integer로 변환하고, toArray()에서 int형 배열로 변경하여 값을 받으려고 했었다. 

하지만 map() 연산을 사용하는 경우 Object 배열로 반환하도록 되어 있어, Integer 배열로는 반환할 수 있으나 int 배열로 변경하려면 직접 int 배열을 생성해서 넣어주어야 했다.

그래서 기본형 스트림을 다루는 mapToInt() 메서드를 사용하여 IntStream으로 변환해 주었고,  toArray()를 통해 바로 int 배열로 정답을 반환할 수 있었다.

 

풀이 2. HashMap과 우선순위 큐(Priority Queue) 사용

- 시간복잡도: O(n log n), LeetCode 13~14초

현재 참고하고 있는 도서에서 두 번째 풀이 방법으로 제시한 내용이다.

앞서 우선순위 큐 파트에서 한 번 사용해 봤지만 빠르게 떠오르지는 않았다.

private int[] topKFrequent_pq_14(int[] nums, int k) {
        // 1. 배열의 요소와 빈도 수를 HashMap에 저장
        // 2. int형 배열을 받는 우선순위 큐에 각 {요소, 빈도 수} 저장. 이 때 빈도 수가 큰 순서대로 저장
        // 3. 반환값인 int형 배열 result 생성, 우선순위 큐를 k만큼 순회하며 요소값인 [0]을 꺼내 저장

        // 1
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int i : nums) {
            frequencyMap.put(i, frequencyMap.getOrDefault(i, 0) + 1); // getOrDefault 사용
        }

        // 2
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        for (int n : frequencyMap.keySet()) {
            pq.add(new int[]{n, frequencyMap.get(n)});
        }

        // 3
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = pq.poll()[0];
        }
        return result;
    }

1) Map에 요소와 빈도 수를 저장하는 부분은 동일하다. 문제는 'PriorityQueue에 어떤 값을 넣어줄 것인가' 였다. 예전 우선순위 큐 문제를 풀 때에는 별도의 클래스를 작성해서 저장했는데, 이번엔 키-값 현태의 데이터들을 비교해야 했기에 간단하게 int 배열로 {키, 값} 형태로 저장하고, Comparator를 value의 자리인 1번째 인덱스를 비교하여 내림차순으로 정렬하도록 구현했다.

2) 우선순위 큐에 값을 저장했다면, k개 만큼 꺼내는 것은 간단하다. 다만 int형 배열로 반환해야 하기에 변수를 별도로 선언을 해준 뒤 PriorityQueue에서 poll()한 값( {키, 값} 형태)에서 필요한 키값(0번째 인덱스)만을 꺼내 저장해주었다.

---

실무에서 Stream API를 사용하는 경우가 많다. 하지만 어떤 원리인지는 자세히 들여다 보지 못한 경우가 많았는데, 이번 문제를 풀며 해당하는 부분을 고민해볼 수 있어서 뜻깊었다. 

알고리즘 문제를 풀면서 Java에 대해 깊이 들여다 보고, 실무에서도 어떤 부분을 적용해볼 수 있을지 고민할 수 있는 부분이 좋고 재미있다. 물론 아직 많이 부족함을 느끼고는 있지만, 꾸준히 하면 나도 모르는 새 한계단 올라갈 수 있을 것이라고 생각한다.

 

<현재 공부중인 알고리즘 도서>

자바 알고리즘 인터뷰 with 코틀린 (박상길 저)