• 값을 비교하지 않는 특이한 정렬
• 자릿수를 정한 다음 해당 자릿수만 비교
• 시간 복잡도는 O(kn)
  • k는 데이터의 자릿수

핵심 이론

• 10개의 큐를 이용
  • 0~9까지를 담기 위해서 10개임
• 각 큐는 값의 자릿수를 대표

• 시간 복잡도가 가장 짧은 정렬

[022] 수 정렬하기 3

• https://www.acmicpc.net/problem/10989
• 기수 정렬을 이용하여 풀기
• N의 최대 개수가 10,000,000으로 매우 크기 때문에 O(nlogn)보다 더 빠른 알고리즘 필요
• 숫자의 크기가 10,000이하라는 것을 바탕으로 기수 정렬과 함께 많이 사용하는 계수 정렬(counting sort)을 사용하여 문제 해결
  • 계수 정렬은 로직이 기수 정렬보다 조금 더 간단
• 숫자의 크기가 10,000이하이므로 10,001 크기의 배열 선언 → 5