[HackerRank] Counting Sort 1

Problem

---

Comparison Sorting
Quicksort usually has a running time of , but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat  (worst-case) running time, since  represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).

 

Alternative Sorting
Another sorting method, the counting sort, does not require comparison. Instead, you create an integer array whose index range covers the entire range of values in your array to sort. Each time a value occurs in the original array, you increment the counter at that index. At the end, run through your counting array, printing the value of each non-zero valued index that number of times.

 

Example

All of the values are in the range , so create an array of zeros, . The results of each iteration follow:

i	arr[i]	result
0	1	[0, 1, 0, 0]
1	1	[0, 2, 0, 0]
2	3	[0, 2, 0, 1]
3	2	[0, 2, 1, 1]
4	1	[0, 3, 1, 1]

The frequency array is . These values can be used to create the sorted array as well: .

 

Note
For this exercise, always return a frequency array with 100 elements. The example above shows only the first 4 elements, the remainder being zeros.

 

Challenge
Given a list of integers, count and return the number of times each value appears as an array of integers.

 

Function Description

Complete the countingSort function in the editor below.

countingSort has the following parameter(s):

• arr[n]: an array of integers

Returns

• int[100]: a frequency array

Input Format

The first line contains an integer , the number of items in .
Each of the next  lines contains an integer  where .

Constraints

Sample Input

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33  

Sample Output

0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2 

Explanation

Each of the resulting values  represents the number of times  appeared in .

---

비교 정렬

퀵 정렬(Quicksort)은 일반적으로 시간 복잡도가 O(nlog⁡n)O(n \log n)O(nlogn)입니다. 그러나 더 빠르게 정렬할 수 있는 알고리즘이 있을까요? 일반적으로, 이는 불가능합니다. 대부분의 정렬 알고리즘은 비교 정렬(comparison sort)로, 즉 리스트의 요소들을 서로 비교하여 정렬합니다. 비교 정렬 알고리즘은 최악의 경우에 O(nlog⁡n)O(n \log n)O(nlogn) 이상의 시간 복잡도를 가질 수 없으며, 이는 각 요소를 어디에 배치해야 할지를 알기 위해 필요한 최소한의 비교 횟수를 나타냅니다. 더 자세한 내용은 제공된 PDF 노트를 참조하십시오.

대안 정렬

카운팅 정렬(Counting Sort)은 비교를 요구하지 않는 또 다른 정렬 방법입니다. 대신, 정렬할 배열의 모든 값 범위를 포함하는 정수 배열을 생성합니다. 원래 배열에서 값이 발생할 때마다 해당 인덱스의 카운터를 증가시킵니다. 마지막으로, 카운팅 배열을 순회하며 비어 있지 않은 인덱스의 값을 그 수만큼 출력합니다.

예시

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

모든 값이 0부터 100 사이에 있으므로, 100개의 0으로 이루어진 배열을 생성합니다. 각 반복의 결과는 다음과 같습니다:

result = [0, 0, 0, 0]

i	arr[i]	result
0	1	[0, 1, 0, 0]
1	1	[0, 2, 0, 0]
2	3	[0, 2, 0, 1]
3	2	[0, 2, 1, 1]
4	1	[0, 3, 1, 1]

최종적으로 생성된 빈도 배열은 [0, 3, 1, 1]과 같이 됩니다. 이러한 값은 정렬된 배열을 만드는 데도 사용할 수 있습니다.

주의사항

이번 과제에서는 항상 100개의 요소를 가진 빈도 배열을 반환해야 합니다. 위의 예시는 처음 4개 요소만 보여주며, 나머지는 0입니다.

도전 과제

주어진 정수 리스트에서 각 값이 나타나는 횟수를 세어 정수 배열로 반환하세요.

함수 설명

아래의 편집기에 countingSort 함수를 완성하세요.

countingSort는 다음 매개변수를 가집니다:

• arr[n]: 정수 배열

반환값

• int[100]: 빈도 배열

입력 형식

첫 번째 줄에는 정수 nnn이 주어지며, 이는 배열의 아이템 개수를 나타냅니다. 그 다음 줄마다 정수 arr[i]arr[i]arr[i]가 주어집니다.

제약 조건

(제약 조건은 원문에 언급되어 있지 않으므로 생략)

샘플 입력

 

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33

샘플 출력

 

0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2

설명

결과 값 각각은 원래 배열에서 나타나는 횟수를 나타냅니다.

 

Solution

---

내가 푼 방식은 아래와 같다. 

class Result {

    /*
     * Complete the 'countingSort' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts INTEGER_ARRAY arr as parameter.
     */
    public static List<Integer> countingSort(List<Integer> arr) {
        // 100개의 요소를 가진 빈도 배열 초기화
        int[] frequency = new int[100];

        // 주어진 배열의 각 값을 빈도 배열에서 카운트
        for (int num : arr) {
            frequency[num]++;
        }

        // 빈도 배열을 List<Integer>로 변환
        List<Integer> result = new ArrayList<>();
        for (int count : frequency) {
            result.add(count);
        }

        return result;
    }
}

 

 

1. 빈도 배열 초기화:
   • int[] frequency = new int[100];를 사용하여 100개의 요소를 가진 배열을 생성
   • 이 배열은 각 숫자가 얼마나 자주 나타나는지를 저장
2. 값 카운트:
   • for (int num : arr) 반복문을 통해 입력 배열 arr의 각 숫자를 확인
   • 해당 숫자의 인덱스에서 빈도 배열의 값을 증가시킨다 (frequency[num]++).
3. 결과 리스트 생성:
   • 최종적으로 빈도 배열을 List<Integer> 형태로 변환하여 반환