7229 : 기수 정렬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
기수 정렬(Radix Sort)은 각 자릿수를 기준으로 정렬을 반복하는 알고리즘입니다.
LSD(Least Significant Digit) 방식은 일의 자리부터 가장 높은 자리까지 정렬을 반복합니다.
시간 복잡도는 $O(d \cdot (N+K))$로, 자릿수 $d$와 기수 $K$에 비례합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
LSD(Least Significant Digit) 방식은 일의 자리부터 가장 높은 자리까지 정렬을 반복합니다.
시간 복잡도는 $O(d \cdot (N+K))$로, 자릿수 $d$와 기수 $K$에 비례합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원소의 개수 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
둘째 줄에 $N$개의 자연수가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 자연수가 공백으로 구분되어 주어집니다.
출력 설명
LSD 방식의 기수 정렬을 구현하여 오름차순 정렬된 정수들을 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
329 457 657 839 436
출력 예시
COPY
복사되었습니다!
복사되었습니다!
329 436 457 657 839도움
각 자릿수마다 카운팅 정렬을 수행합니다.
digit = (num // exp) % 10으로 현재 자릿수를 추출하고, 카운팅 정렬 후 exp *= 10을 반복합니다.