문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

Comparison Sorting

Quicksort는 대게 n X lon(n)의 실행 시간을 가지지만 더 빠르게 정렬하는 알고리즘이 있을까? 일반적으로 가능하지 않다. 대부분 정렬 알고리즘은 비교 정렬이다. 예를 들면 리스트의 요소들을 서로 비교하여 정렬한다. 비교 정렬 알고리즘은 최악의 경우 n X log(n)의 실행시간을 뛰어넘을 수 없다. n X log(n)은 각 요소를 배치할 위치를 알기 위해 필요한 최소 비교 횟수를 나타낸다.

Alternative Sort

또 다른 정렬 메소드 카운팅 정렬은 비교가 필요하지 않다. 대신에 정렬할 배열에 값의 전체 범위가 포함하는 정수형 배열을 생성한다. 최초의 배열에 값이 나타날때 마다 해당 인덱스의 카운트를 증가시킨다. 카운팅 배열을 통해 실행이 끝나고, 각각의 0이 아닌 인덱스의 값만큼 출력해라.

Example

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

모든 값들은 0에서 3까지의 범위에 있고 result = [0, 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, 1, 1, 1]
4	1	[0, 3, 1, 1]

빈도 배열은 [0, 3, 1, 1]이다. 이 값들을 사용해서 sorted = [1, 1, 1, 2, 3]의 정렬된 배열을 만들 수 있다.

Function Description

countingSort 함수를 완성해라.
countingSort 함수는 아래와 같은 매개변수를 가지고 있다.

• arr[n]: 정수형 배열

Returns

• int[100]: 빈도 배열

Constraints

• 100 <= n 10^6
• 0 <= arr[i] < 100

Solved

정수의 개수를 담을 countingArr를 생성한다. 이때 countingArr의 인자 수는 100으로 초기화한다. Constraints를 보면 arr의 사이즈가 100까지라고 알려주고 있다. (왜 맞은 거지?)

int[] countingArr = new int[100];

반복문을 통해 해당 값을 통해 인덱스를 증가시킨다.

for(int i : arr){
	countingArr[i]++;
}

결과로 반환할 리스트 result를 생성하고, 반복문을 통해 countingArr의 요소를 추가시킨다.

List<Integer> result = new ArrayList<>();

for(int i : countingArr){
	result.add(i);
}

마지막에 result를 반환한다.

return result;

All Code

public static List<Integer> countingSort(List<Integer> arr) {
	int[] countingArr = new int[100];

	for(int i : arr){
		countingArr[i]++;
	}

	List<Integer> result = new ArrayList<>();

	for(int i : countingArr){
		result.add(i);
	}

	return result;
}