[10989]수 정렬하기 3

10989번: 수 정렬하기 3

 

www.acmicpc.net

/*10989번 수 정렬하기 3*/
#include <iostream>
using namespace std;
int Arr[10001];
int N;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N;
	int a;
	for (int i = 1; i <= N; i++) {
		cin >> a;
		Arr[a]++;
		//cin >> Arr[i];
	}

	
	for (int i = 1; i <= 10000; i++) {
		int b = Arr[i];
		for (int j = 0; j < b; j++) {
			cout << i<<'\n';
		}
	}
}

이 문제는 N범위가 1억이라 보통 정렬 방식을 사용하면 메모리초과 또는 시간초과가 발생한다.

유심히 봐야할 점은 입력 정수의 범위가 10000까지라는 점을 이용해서 

입력 받은 수에 맞는 배열 번호에 하나씩 추가하면된다.

출력은 배열 1번방 부터 들어있는 숫자만큼 반복해서 출력을 해주면 된다.