10989번 수 정렬하기 3

문제링크 : www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

이 문제는 카운팅 정렬을 이용해 푸는 문제입니다.

<카운팅정렬(Counting Sort) 알고리즘>

1. 배열의 처음부터 끝을 돌며 각 요소들이 몇번씩 등장하는지 세서 counting 배열 생성

    ex ) A 배열의 i번째 수가 1이라면, counting[1]+=1을 해줌

2. counting 배열을 작은 수부터 돌며 각 수가 몇번 등장했는지를 통해 새로운 배열 생성

    ex) counting[i] = 2 라면 i가 2번 들어가게 배열B 생성.

예제

+) 참고 : soobarkbar.tistory.com/101

계수 정렬 (Counting Sort)

 

#include <iostream>

int main() {
	int T = 0;
	scanf("%d", &T);
	
	int number[10001] = { 0 };
	int max = 0;
	for (int i = 0; i < T; i++) {
		int n = 0;
		scanf("%d", &n);
		number[n]++;
		if (max < n) max = n;
	}
	for (int i = 1; i < max+1; i++) {
		if (number[i] > 0) {
			for (int j = 0; j < number[i]; j++) {
				printf("%d\n", i);
			}
		}
	}

	return 0;
}