[C] 백준 | 10989번 코드 - 수 정렬하기 3

>문제

> 핵심

- 모든 값을 배열에 저장할 필요가 없다.

- "이 수는 10,000보다 작거나 같은 자연수이다" 

>풀이과정

지금껏 qsort나 합병정렬, 버블정렬같은 학교에서 배운 정렬만 쓰던 나에게 엄청난 깨달음을 주게하는 문제다..

 

평소에 하던대로 값을 배열에 모두 입력받은 후에 통으로 정렬을 하게되면

시간초과 혹은 메모리초과가 필연적으로 발생하게 된다.

 

힌트는 "이 수는 10,000보다 작거나 같은 자연수이다" 에 있다.

 

10,000보다 작은 자연수.

10,000칸 짜리 int 배열을 만든 후(0으로 모두 초기화),

[입력받은 값 - 1]의 인덱스를 찾아 해당 값을 +1 해주는 방식을 떠올렸다.

 

솔직히 풀긴 풀었지만 힌트 안봤으면 나도 이런 생각을 전혀 못했을 것 같다. 

틀에박힌 사고방식을 벗어나야 풀 수 있는 문제인 것 같다.

 

>깨달은점

틀에박힌 생각을 버리자.

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int board[10000] = { 0 };
	int i, n, tmp;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf(" %d", &tmp);
		board[tmp - 1] += 1;
	}

	for (i = 0; i < 10000; i++)
	{
		if (board[i] == 0)
			continue;
		else
		{
			while (board[i] > 0)
			{
				printf("%d\n", i + 1);
				board[i] -= 1;
			}
		}
	}

	return 0;
}