#10989. 수 정렬하기 3

문제링크

Problem

• 시간 제한 3초
• 메모리 제한 8MB

Goal : 주어진 수를 오름차순으로 정렬하기

Solution

• 메모리 제한이 8MB라는 점에 주의한다.
• 주어진 수는 최대 천만
  수의 최댓값은 최대 만
• int 형 배열을 천만개 크기로 만들면
  10000000 * 4 = 4천만 byte = 38…MB(이미 초과
• 하지만 10001 크기의 배열만으로 문제를 풀 수 있다.
  40004 = 0.038..MB(충분히 통과)
• 위의 크기만 가지고 문제를 푸려면 counting sort가 적절하다.
• 입력으로 받은 수를 각각 세어준다. → 끝
• ??? 진짜 끝이다. 남은건 해당 숫자만큼 차례대로 카운트한 횟수만큼 출력해주면 된다.

1 Try

#include <cstdio>
#define MAX 10000
using namespace std; // 이거 안써도 된다...
int cnt[MAX+1];
int main()
{
	int n, input;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &input);
		cnt[input]++;
	}
	for(int i = 1; i <= MAX; ++i) {
		for(int j = 0; j < cnt[i]; j++) {
			printf("%d\n", i);
		}
	}
	return 0;
}