1) O(n) 정렬


3 8 2 4 5 9 10 2 8 10 3 3 7 5 10 2 8 9 4 1 1 9 10 2 5


위 수의 특징은 모든 원소가 10 이하라는 것에 착안한다.

이와 같이 원소의 range가 원소의 개수에 비해 상당히 좁을 때는, 공간을 더 사용함으로써 시간을 줄이는 정렬 테크닉을 사용할 수 있는데

이를 count sort라고 한다.


for(int i=0; i<n; i++)

{

int k;

scanf("%d",&k);

arr[k]++;

}


for(int i=1;i<=10;i++)

{

for(int j=0;j<arr[i];j++) printf("%d ",i);

}



2) 알파벳 개수 세기


먼저 모든 문자열이 알파벳 대문자라는 전제하에 진행한다.

char가 ASCII 임을 이용하여 쉽게 개수를 셀 수 있다.


for(var i=0; i<str.length; i++)

{

arr[str.charAt(i)-'A']++;

}