baekjoon 10989

https://www.acmicpc.net/problem/10989

---

Idea

처음엔 그냥 젤 빠른 Quick Sort쓰면 되는 거 아님? 하고 제출했는데 메모리 초과 ㅋㅋ
내 코딩 세계에서 제일 효율 좋고 빠르다고 생각되던 Quick Sort 알고리즘이 또 실패했다.
c언어에 내장 되어있는 qsort도 써봤지만 똑같이 메모리 초과라는 채점결과가 나왔다.

문제를 딱 처음 봤을 때 입력과 출력에 같은 숫자가 두 번 세 번씩 나온다는 건 대수롭지 않게 넘겼지만 여기서 힌트를 얻었다. 입력은 어쩔 수 없이 10,000,000번 이하로 받아야 하니 최대 10,000,000번 이고 출력할 때 메모리를 아끼면 되지 않을까?

아니나 다를까 여기에 맞는 알고리즘이 있었다. Counting Sort라고 간단하게 설명하면 요소 값들끼리 서로 비교하지 않고 정렬하는 알고리즘이다. 뭔 개소린가 싶었지만 코드도 되게 쉽고 간편하고 정말 효율적이었다.

유레카 이마 탁..

---

Code

#define _CRT_SECURE_NO_WARNINGS
#define MAX 10001
#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int count[MAX] = { 0, };
	int N, num;

	scanf("%d", &N);

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

	for (int i = 0; i < MAX; i++) {
		if (count[i] == 0) {
			continue;
		}

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

	return 0;
}