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

Problem

종종, 리스트가 정렬될때 정렬된 요소들은 다른 값들의 키이다. 예를 들어 만약 파일을 크기별로 정렬한다면 크기는 각 파일에 대한 크기 정보와 연결되어 있어야 한다. 크기 숫자를 가지지 못하고 순서대로 출력할 수 없고, 필요한 모든 파일의 정보를 출력해야 한다.
카운팅 정렬은 정수형 리스트를 정렬할 때 사용된다. 비교하는 것보다 정렬할 배열의 값 범위를 전체적으로 포함하는 정수형 배열을 만드는게 낫다. 원래 배열에서 각각의 값이 나타날때 해당 인덱스의 카운터를 증가시킨다. 카운팅 배열의 실행이 끝나고 각 인덱스의 값이 0이 아닌 것들을 반복해서 출력해라.
예를 들어 arr = [1, 1, 3, 2, 1]인 배열이 있다고 생각하자. 모든 값은 [0..3]의 범위 안에 있고, 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]

지금 정렬된 배열 sorted = [1, 1, 1, 2, 3]을 출력할 수 있다.

Function Description

countingSort 함수를 완성해라. 원래 배열을 오름차순으로 정렬한 정수형 배열을 반환해라.
countingSort 함수는 아래와 같은 매개변수를 가지고 있다.

• arr: 정수형 배열

Constraints

• 0 <= n <= 1000000
• 0 <= arr[i] < 100

Solved

크기가 1000000인 배열을 먼저 선언하고 인자로 받은 arr을 반복문을 통해 해당 인덱스의 값을 증가 시킨다.

int[] result = new int[1000000];

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

반환할 리스트 sorted를 생성하고, 반복문을 통해 result를 순회한다. 이때 result[i]의 값이 0이면 sorted에 추가하지 않고 0이 아니면 해당 값만큼 인덱스를 sorted에 추가한다. 반복문이 끝나면 sorted를 반환한다.

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

for(int i = 0; i < result.length; i++){
	if(result[i] != 0){
		for(int j = 0; j < result[i]; j++){
			sorted.add(i);
		}
	}
}

return sorted;

All Code

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

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

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

	for(int i = 0; i < result.length; i++){
		if(result[i] != 0){
			for(int j = 0; j < result[i]; j++){
				sorted.add(i);
			}
		}
	}

	return sorted;
}