[백준] [C] 10989번 : 수 정렬하기 3

문제

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

입력

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

출력

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

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

알고리즘 [ 접근방법 ]

앞선 포스팅 수 정렬하기 2 와 동일한 문제이지만 문제 조건이 조금 다른 문제이다. 메모리 제한이 8MB로 현저히 적기 때문에 Bubble Sort나 Merge Sort를 사용하게 되면 메모리 초과로 오답이라고 나온다. 그러나 이번 문제는 입력받는 수가 10,000보다 작거나 같은 자연수라는 새로운 조건이 있으므로 counting 방식을 사용해 풀 수 있다.

먼저 수를 입력 받고 입력받은 수에 해당하는 인덱스에 +1을 해준다.

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

예를들어 5를 입력받으면 count[5]++가 되어, count={0,0,0,0,1,0,0,0…}와 같은 구조가 되는것이다.

이어서 for문을 이용해 이를 출력해주면 된다! 단 같은수가 여러번 입력 받은 경우를 처리해주기 위해 이중for문을 사용해야한다.

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

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

	scanf("%d", &n);

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

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