[C언어] 백준 10989 : 수 정렬하기 3
https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html 카운팅 정렬 예시
https://soobarkbar.tistory.com/101 카운팅 정렬 이해
위의 예시로 풀이를 해보자면 5 2 3 1 4 2 4 5 1 7의 숫자들이 있다. 여기서 각 숫자의 빈도수를 계산하여 배열에 집어 넣는다.
0 1 2 3 4 5 6 7
0 2 2 1 2 2 0 1
이렇게 빈도수를 구 할 수 있다. 그리고 이 빈도수를 토대로 0에서 순차 탐색을 진행하면 된다.
0은 빈도수가 0, 패스
1은 빈도수가 2, 1을 두 번 출력
2는 빈도수가 2, 2를 두 번 출력
3은 빈도수가 1, 3을 한 번 출력
4는 빈도수가 2, 4를 두 번 출력
5는 빈도수가 2, 5를 두 번 출력
6은 빈도수가 0, 패스
7은 빈도수가 1, 7을 한 번 출력
배웠던 것 처럼 누적합을 구하는 방식으로도 할 수 있지만, 이 문제에서는 메모리제한으로 안되는걸 확인했다.
그래서 위 방법대로 진행한다.
https://kindload-save.tistory.com/49 아이디어 참조
풀이
#include <stdio.h>
int arr[10001];
int main()
{
int n, j;
int ins;
scanf("%d", &n);
int i = 1;
while(i <= n)
{
scanf("%d", &ins);
arr[ins]++;
i++;
}
i = 1;
while(i <= 10000)
{
j = 1;
while(j <= arr[i])
{
printf("%d\n", i);
j++;
}
i++;
}
}
Author And Source
이 문제에 관하여([C언어] 백준 10989 : 수 정렬하기 3), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmainsain/C언어-백준-10989-수-정렬하기-3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)