[BOJ] 10989. 수 정렬하기 (C)

• 코딩 초보. 

---

10989. 수 정렬하기 

 

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

---

 

1.C

 

중복된 수를 정렬해야할 때도 존재하므로, 이번에는 counting sort(계수정렬)의 방법을 공부해서 코드를 구현해보았다. 

#include <stdio.h>

main() {
	int n,k; 
	int a[10001] = { 0, }; 

	scanf("%d", &n); 
	for (int i = 0; i < n; i++) {
		scanf("%d", &k);
		a[k] += 1; 
	}

	for (int i = 0;i<10001; i++) {
		for (int j = 0; j < a[i]; j++) {
			printf("%d\n", i); 
		}
	}
}

먼저 내가 공부한 counting sort에 대해 대략 설명하겠다.

 

counting sort는 누적합을 사용한다. 

예를 들어 1 3 2 4 5 1 1 2 2 3 7 의 배열이 주어진다고 하면, 

1은 총 3, 2는 3, 3은 2, 4는 1, 5는 1, 7은 1번이 나온다. 

여기에서 counting sort는 누적합을 사용한다. 

 

1은 3

2는 5 (2+3)

3은 7(2+3+2)

4는 8(2+3+2+1)

5는 9(2+3+2+1+1)

7은 10(2+3+2+1+1+1)

 

이런식으로 count(누적합)를 따로 저장해두는 배열을 만들어주는 것이다. 그리고 누적합을 인덱스처럼 접근하여 차례대로 배열에 배정해주는 방식인데 위 문제를 풀때는 이런 방향으로 구현하지는 않았다. 

 

위 코드는 누적합이 아니라 수의 개수를 배열의 인덱스에 저장하도록 하였다. 

그러니까 10001까지의 인덱스에 차례대로 해당 인덱스에 수가 나온 횟수를 저장해준 것이다. 0이면 아무것도 출력을 안하게 되고, 하나 이상이 있으면 그만큼 차례대로 출력을 하도록 하면 된다. 

(참고한 글: https://bowbowbow.tistory.com/8 ) 

 

---