백준 10989번 : 수 정렬하기3( count 정렬)

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

10989번: 수 정렬하기 3

입력

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

출력

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

 

문제포인트

1.count정렬 이용

2.시간초과와 메모리초과 고려

 

count정렬 이란?
입력하는 값을 index로하는 배열을 생성하고 그 배열에 입력값 나오는 갯수만큼 값을 저장한다.

그리고 최솟값부터 최댓값까지 값만큼 출력한다.

#include<iostream>
#include<vector>
#include<cmath>
#include <algorithm>
using namespace std;
int main()
{	
	cin.tie(NULL);                       //cin,cout 시간이 오래걸리기때문에 시간 줄이기
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	int count[10001] = { 0 };                   //최고값까지의 숫자별 빈도수 및 누적함
	int t,n;
	int max = 0;
	cin >> t;
	for (int i = 0; i < t; i++) {          //숫자 크기를 index로 하는 count배열에 나오는 갯수를 값으로 지정
		cin >> n;
		count[n]++;
		if (max < n)
			max = n;
	}
	for (int i = 1; i <= max; i++) {       //작은수부터 나오는 갯수만큼 출력하고 0이면 출력안함
		while (count[i]) {
			cout << i << '\n';
			count[i]--;
		}
	}
	return 0;
}