99클럽 코테 스터디 32일차 TIL Top K Frequent Elements feat. CountingSort

알고리즘

99클럽 코테 스터디 32일차 TIL Top K Frequent Elements feat. CountingSort

ernest45 2024. 6. 20. 21:52

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

priorityQueue

map

map.merge

counting sort

1. 문제 및 접근

347. Top K Frequent Elements

map으로 관리

31일차 문제와 너무 유사

priorityQueue로 우선순위를 빈도의 내림차순으로 주고 K개만큼 뽑기

++counting sort 방식 추가

문제가 이해하기 힘들어서 내 영어 실력의 문제인가 했지만, 댓글들을 보니 전세계인들이 화나있다

불친절한 리트코드..

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.

2. 풀이

31일차 문제랑 별로 다를 게 없어 보고오면 좋다.

궁금하면 더 자세한 걸 보고오자. 거의 유사하고 더 자세히 적어놈

99클럽 코테 스터디 31일차 TIL Sort Characters By Frequency feat. Comparator vs Comparable

https://leetcode.com/problems/sort-characters-by-frequency/submissions/1293844763/ getOrDefualtpriorityQueuemaxHeapmapEntry 1. 문제 및 접근 주어진 s를 나타나는 빈도수에 대해 내림차순으로 반환같은 수의 빈도라

ernest45.tistory.com

public int[] topKFrequent(int[] nums, int k) {

    int answer[] = new int[k];

    HashMap<Integer, Integer> map = new HashMap<>();


    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }


    PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new PriorityQueue<>(
            (a, b) -> b.getValue().compareTo(a.getValue()));
    // 람다로 내림차순 정렬

    maxHeap.addAll(map.entrySet());

    for (int i = 0; i < k; i++) {

        Map.Entry<Integer, Integer> entry = maxHeap.poll();
        int now = entry.getKey();
        answer[i] = now;

    }
    
    return answer;

}

전체풀이

문제 이해가 어려웠다.

나만 그런 게 아니라 다행

nums = {1, 1, 1, 2, 2, 3}

k = 2

배열과 k가 주어지는데, 배열 안에서 반복되는 횟수가 많은 순서대로 k개만큼 배열로 출력하면 된다.

다들 헷갈려해서 댓글들을 보니, 화가 많아 보였다.. ㅎ

num 배열에서

1은 3번 반복,

2는 2번 반복

3은 1번 반복한다.

k가 2라면,

answer = [1,2]로 순서가 1이 더 많으니 첫 번째, 2는 두 번째로 위치한 채로 출력

같은 빈도라면 아무거나 출력해도 상관 없다고 함

2-1. Map

ex) nums = [1, 1, 1, 2, 2, 3] , k = 2

k개만큼 출력할꺼니까, answer 배열을 k개로 선언

들어온 num 배열을 돌면서

map.put()

key = nums의 요소

value = num의 key를 찾아서 2개의 경우가 있다.

key가 있다면 ? value 값을 가져와 +1
key가 없다면 ? defaultValue로 넣어주게 되는데 이 경우 0으로 지정

이렇게 되면 같은 key를 만나게 되면 빈도가 +1 될 것이다.

++ map.merge()라는 더 간편한 메서드를 지원한다. 한번 포스팅 해봐야겠고, 다음에 써서 보여주겠다!

2-2. priorityQueue

Map.Enrty 타입의 maxHeap 선언

java의 정렬의 기본 값은 오름차순이기 때문에, 우리는 따로 maxHeap을 만들기 위해 람다식으로

내림차순으로 만들어줌

우선순위를 value값의 내림차순으로 주는 것

우리는 value(빈도)를 기준으로 정렬할 것이기에 value를 비교

만든 priorityQueue에 map.entrySet을 넘겨 모두 추가

우선순위에 따라 하나씩 꺼내, key 값을 정답 배열에 k번 돌면서 하나씩 추가

(우선순위 큐를 쓰는 이유다)

Q)
nums = {1, 1, 1, 2, 2, 3}

k = 2

A) answer = {1, 2}

3. 다른 풀이(counting sort란)

카운팅 정렬은 입력 배열의 크기에 비해 비교적 많은 메모리를 사용하지만,

입력 배열의 범위가 작고 정수로 제한되어 있을 때 매우 효율적인 정렬 알고리즘

Counting Sort ?

계수정렬이라고도 불리며, O(N)의 시간 복잡도를 가지고 있는 엄청 빠른 정렬 방법
동일한 값을 가지는 데이터의 상대적인 순서가 유지 돼 안정적이다.

사실 시간 복잡도는 O(N + K) n = 데이터의 수, k는 데이터의 최대 값

엄청 빠른 정렬방법인데 왜 기본적으로 O(NlogN)의 방식들을 쓸까 ?

단점도 있는데,

count해서 정렬하는 방식이라 데이터의 범위가 크면 데이터를 담는 배열의 크기도 엄청 커짐
수열의 길이보다 데이터의 범위가 극단적으로 크다면 엄청난 저장공간이 사용되는 단점

(Quick 정렬의 경우 시간복잡도 평균값이 O(NlogN) 으로 빠른편이면서 배열도 하나만 사용하기 때문에

공간복잡도는 𝚶(N)으로 시간과 메모리 둘 다 효율적이라는 점이다. ~~최악의 경우 O(N^2)지만..~~)

상황에 맞게 잘 쓰자!

counting Sort 과정

카운트 배열 생성 : 주어진 배열의 값의 수를 세어 count 배열에 저장. count 배열의 index = 그 숫자, 값은 등장 횟수
누적합 배열 생성 : 카운트 배열을 기반으로 누적합 배열 생성. 각 수가 정렬된 배열의 위치를 뜻함 * 숫자의 누적합은 이전 숫자의 등장횟수
정렬된 배열 생성 : 누적합을 역순으로 순회하며 정렬 위치 배치. 숫자가 나올 때 마다 count 배열의 등장 횟수를 감소

코드를 보여주며 설명하겠다.

3-1. Counting Sort

예제로

int arr[] = new int[] {4, 2, 2, 8, 3, 3, 1};

public void countingSort(int[] arr) {

    if (arr.length == 0) {
        return;
    }
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    int range = max - min + 1;

    // 카운트 배열과 출력 배열 생성
    int[] count = new int[range];
    int[] output = new int[arr.length];

    // 카운트 배열 초기화
    for (int i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }

    // 카운트 배열의 누적합 계산
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // 출력 배열에 정렬된 값 저장
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    // 원본 배열에 정렬된 값 복사
    for (int i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}

3-2. count 해줄 배열 범위

기본적으로 세어줄 배열을 하나 만들어야하고,

그 배열의 size는 최대값에 크기가 결정된다.

그러나 음수가 오지 않는다고 가정한다면 최대 값으로만 찾으면 되나,

음수의 가능성이 있기에

arr의 max와 min 값을 찾아 범위를 지정해준다.

arr = {4, 2, 2, 8, 3, 3, 1}가 있다고 한다면

range = 8이 나온다.

3-3. count 해줄 배열 생성

구한 범위만큼의 count 배열과

정렬 후 담을 배열을 만들어주기

3-4. Count배열 초기화

핵심인 로직이다. 설명을 하자면

arr = {4, 2, 2, 8, 3, 3, 1}

각 arr 요소의 값에 따라 count 배열의 index에 하나씩 증가 시켜주는 것이다 !

첫 요소인 4를 예로 들자면 count 배열의 4번째 위치에 하나를 세어주는 것이다!

arr[0] 4의 경우, count 인덱스 4 - 1 = 3에 카운트 증가: [0, 0, 0, 1, 0, 0, 0, 0]
arr[1] 2의 경우, count 인덱스 2 - 1 = 1에 카운트 증가: [0, 1, 0, 1, 0, 0, 0, 0]
arr[2] 2의 경우, count 인덱스 2 - 1 = 1에 카운트 증가: [0, 2, 0, 1, 0, 0, 0, 0]
arr[3] 8의 경우, count 인덱스 8 - 1 = 7에 카운트 증가: [0, 2, 0, 1, 0, 0, 0, 1]
arr[4] 3의 경우, count 인덱스 3 - 1 = 2에 카운트 증가: [0, 2, 1, 1, 0, 0, 0, 1]
arr[5] 3의 경우, count 인덱스 3 - 1 = 2에 카운트 증가: [0, 2, 2, 1, 0, 0, 0, 1]
arr[6] 1의 경우, count 인덱스 1 - 1 = 0에 카운트 증가: [1, 2, 2, 1, 0, 0, 0, 1]

(1은 1개, 2은 2개, 3은 2개 ...)

이래서 최대 값만큼의 size가 필요!

3-5. 누적합 계산

카운트 배열의 누적합들을 더해준다.

우리는 누적합으로 그 숫자의 위치를 알 수 있다!

어떻게 누적합으로 자리를 알 수 있을까 ?

우리는 숫자를 세어주고, 그 숫자만큼 더해줘서 각 index에 해당하는 숫자가 몇개가 있는 지 아는 count 배열이 있다.

(1은 1개, 2은 2개 ~)

거기서 누적을 하게 된다면 각 인덱스 별로 몇개씩 있는 지 범위가 산정될 것이다.

누적합을 이용해 정렬된 배열을 생성하는 방법은

1. 원본 배열을 뒤에서부터 순회하며 누적합 배열을 참조하여 정렬된 배열에 각 숫자를 배치

2. 각 숫자를 배치할 때마다 누적합 배열의 값을 감소

Q) 왜 뒤에서 부터 찾아? 앞에서 찾아도 되잖아

a) 뒤에서 부터 찾는 이유는 아까 말한 Counting sort 장점인 안정성 때문!

앞에서부터 순회하면 동일한 숫자의 위치가 꼬일 수 있어서,

뒤에서부터 순회하여 각 숫자가 누적합 배열을 참조하여 정렬된 위치에 올바르게 배치 하는 것

한마디로 같은 수가 들어오면 순서는 뒤에서부터 채워줘야 하는데,

우리는 값으로 몇번 나왔는지 + 갈 index의 값을 가지고 있다.

2의 경우 2번 count 됐고, index[2]의 자리에 있어야 한다.

2의 경우가 두 번 count 됐다고 예시를 들자면

2가 들어갈 자리는 index[1~2] 이다.

뒤에서 부터 찾으면 count가 줄어들면서, -1 되기 때문에 [2], [1] 이 순으로 자리가 맞아야 한다

앞에서 부터 찾게 된다면

처음 2는 index[2] 위치할 것이고,

다음 2는 index[1] 에 위치할 것이다.

([1],[2]가 올바름)

arr = [4, 2, 2, 8, 3, 3, 1]

output = [1, 2, 2, 3, 3, 8]

arr[1] = 2는 output[1] 이여야 한다.

arr[1] = 2가 output[2] 에 오면 안정성을 보장하지 못하기에(위치가 바꼈다고 할 수 있음)

어렵다면 이것만 기억하자

arr에서의 같은 값이라면 원래의 순서를 유지해야 안정적이라고 할 수 있다!

3-6. 실제 index 찾아가기

말한대로 뒤에서 찾는데,

실제 정렬된 배열 output은 count[]의 arr[i]값의 인덱스를 가지고 있다.

그리고 count 배열에서 하나를 계산해줬으니, 계산할 때 마다 빼주기!

1회차 :

i = 6

1회차의 arr[6] 의 값은 1이다.

1이 어디에 가야 하는 지 알기 위해서는 count[arr[6]] = count의 "첫 번째 "에 적혀있다.

count 배열에서 보니 첫번 째 위치로 가라!

output 배열에 첫 번째에 그대로 적어주고, count의 첫 번째의 값을 감소

2회차 :

i = 5

2회차의 arr[5] 의 값은 3이다.

3이 어디가야 하는 지 알기 위해서 count[arr[3]] = count의 " 세 번째 " 에 적혀있다.

count 배열에서 보니 다섯 번째 위치로 가라!

output 배열에 다섯 번째에 그대로 적어주고, count의 세 번째의 값을 감소

이런 식으로의 반복이 계속된다면

기본 배열의 arr가 output으로 오름차순 정렬 완료된다.

복사하면 끝 !

솔직히 직관적으로 이해하기 힘들다.. 나도 어려웠고 하나 하나 흐름을 찾아 가는 게 더 편할 것이다.

이해를 위해 애니메이션과 좋은 예시를 드는 블로그를 추가해놓겠다.. 파이팅 ㅠㅠ

애니메이션

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort

This is an animation of the counting sort algorithm found in CLR's Algorithms book. Array C (counting array): PSEUDOCODE FOR COUNTING SORT (taken from CLR) Initialize counting array to all zeros. Count the number of times each value occurs in the input. Mo

www.cs.miami.edu

알고리즘 정리 끝판왕 블로그

https://st-lab.tistory.com/104

자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)

[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) - [현재 페이지] 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (Heap Sort) 7. 합병(

st-lab.tistory.com

누적합이 이해 안간다면 ?

https://bowbowbow.tistory.com/8

Counting Sort : 계수 정렬

Counting Sort Counting Sort Counting Sort 소개 정렬 과정 애니메이션 예시 구현 정리 끝 소개 Counting Sort는 정렬 알고리즘으로 의 시간복잡도를 갖습니다. 반면 일반적 상황에서 가장 빠른 정렬 알고리즘

bowbowbow.tistory.com

4. 어떻게 counting Sort로 이 문제를 풀 것인가 ?

생각해보면 간단하다.

우리가 원하는 건 빈도에 따라 k개 만큼 정렬된 배열의 실제 값들이 궁금한 것이다.

counting Sort는 원하는 빈도도 우리가 계산했고, 또 내림차순으로 정렬만 하면 될 것이기에

이 문제에 완벽하다고 할 수 있다.

입력 범위도 -10^4 <= i <= 10^5 라 크지 않다.

(min,max 편차를 알 수 없어 조금 불편하긴 하지만)

public int[] countingSort(int[] arr, int k) {

    if (arr.length <= 1) {
        return arr;
    }
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int num : arr) {
        if (num < min) {
            min = num;
        }
        if (num > max) {
            max = num;
        }
    }
    int range = max - min + 1;


    // 카운트 배열과 출력 배열 생성
    int[] count = new int[range];
   

    // 카운트 배열 초기화
    for (int i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }


    List<Integer>[] frequencyList = new List[arr.length + 1];
    for (int i = 0; i < frequencyList.length; i++) {
        frequencyList[i] = new ArrayList<>();
    }

    // 빈도수 별 숫자 저장
    for (int num = min; num <= max; num++) {
        int frequency = count[num - min];
        if (frequency > 0) {
            frequencyList[frequency].add(num);
        }
    }

    // 결과 배열에 상위 k개의 숫자 저장
    int[] result = new int[k];
    int idx = 0;
    for (int freq = frequencyList.length - 1; freq >= 0; freq--) {
        List<Integer> list = frequencyList[freq];
        for (int num : list) {
            result[idx++] = num;
            if (idx == k) {
                return result;
            }
        }
    }

    return result;}






public int[] topKFrequent(int[] nums, int k) {



    HashMap<Integer, Integer> map = new HashMap<>();


    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    // Step 2: 빈도수를 배열에 저장합니다.
    int[] frequencyArray = new int[map.size()];
    int index = 0;
    for (int count : map.values()) {
        frequencyArray[index++] = count;
    }








    int[] sortedArray = countingSort(frequencyArray, k);

    return sortedArray;

}

5. 마무리

카운팅소트를 활용할 생각은 못했는데,

역시 많은 걸 알아야 한다고 느꼈다.

여러 방식을 알다보면 장점만 취합해서 가능할 것 같다..

countingSort의 정확한 동작원리가 어려워서 미루다 직접 구현해보니, 재밌기도 하고 다른 정렬 방식들도

시간되면 계속 구현해봐야겠다..