10989번: 수 정렬하기 3 (acmicpc.net) 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 수의 개수의 범위가 상당히 크다. 천만개.. 일단 시간복잡도를 고려하면 O(NlogN)을 사용해야할 생각을하겠다. 이 문제의 경우 하지만 더 좋은 시간복잡도를 활용할수있는 정렬 알고리즘이 있는데 바로 카운팅 정렬이다. 카운팅 정렬은 일반적으로 이 문제와 같이 input받는 정수의 범위가 주어질때 유용하다. 시간복잡도는 O(N+K)이지만. 이상적으로 웬만하면 O(N)에 수렴한다. 즉 상당히 효율적인 정렬이라고 할 수 있다. 또한 ..