7228 : 계수 정렬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
계수 정렬(Counting Sort)은 원소의 값을 인덱스로 활용하여 정렬하는 알고리즘입니다.
비교 기반 정렬의 하한인 $O(N \log N)$을 뛰어넘어 $O(N+K)$ 시간 복잡도를 달성합니다.
단, 원소의 범위 $K$가 크면 메모리 사용량이 증가합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
비교 기반 정렬의 하한인 $O(N \log N)$을 뛰어넘어 $O(N+K)$ 시간 복잡도를 달성합니다.
단, 원소의 범위 $K$가 크면 메모리 사용량이 증가합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 $N$이 주어집니다. ($1 \le N \le 1{,}000{,}000$)
둘째 줄에 0 이상 1,000,000 이하인 $N$개의 정수 $K$가 주어집니다.
둘째 줄에 0 이상 1,000,000 이하인 $N$개의 정수 $K$가 주어집니다.
출력 설명
계수 정렬을 활용해 오름차순 정렬한 결과를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
3 1 4 1 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 1 3 4 5도움
크기 $K+1$인 카운트 배열을 만든 뒤, 각 원소의 등장 횟수를 기록합니다. 그 후 인덱스 순으로 카운트만큼 출력합니다.