출처 BOJ

수 정렬하기 3

문제

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

입력

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

출력

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

예제

범위체크

$10,000 <= INT$
(범위를 변경시키는 연산없음)

풀이

단순하게 sort함수 사용할 경우
sort 시간복잡도 $= nlog(n) = 10^7log10^7$
→ 오래걸림

다른방법
입력받으면서 count, 출력할때 count수만큼 반복출력

코드

code

#include<cstdio>
#define MAX 10100

using namespace std;

int main(){
	int N;
	int cnt[MAX]={0};
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		int temp;
		scanf("%d",&temp);
		cnt[temp]++;
	}

	for(int i=0; i<MAX; i++){
		while(cnt[i]--)
			printf("%d\n",i);
	}
}

복잡도

$O(N+10,000)$ N = 숫자의 개수
10,000 = 가능한 가장 큰 수
for문을 0부터 가장 큰수까지 돌고 + 겹치는 경우를 printf하기 때문