10989번 수 정렬하기(counting sort) - ☆
#문제링크
1. https://www.acmicpc.net/problem/2750
2. https://www.acmicpc.net/problem/2751
3. https://www.acmicpc.net/problem/10989
N개의 입력값을 받아 오름차순으로 정렬하는 문제로, <algorithm>헤더에 있는 sort함수를 사용하여 간단하게 풀 수 있다.
<메모리 8MB제한 정렬>
그냥 sort함수로는 재귀호출이 잦아서 그런지 메모리초과가 뜬다. 방법을 찾던 중에 어떤분의 질문에 대한 답글을 보고 Counting 정렬이라는 것이 있다는걸 알게 됐다. Counting정렬은 원본 배열의 요소값, 예를들어 원본 배열을 A라 할때, A[0]의 값이 7이라 하면, 그 7이 원본 배열에 몇개 있는지를 세어서 Counting배열에 담는다. Counting배열을 C라 하고, A에 7이 4개 있다고 치면, C[7]=4가 되는 것이다. 여기서 각 C배열의 누적합을 계산한다. C[i] = C[i]+C[i-1]로 누적합을 계산해서 7이라는 값의 최대인덱스 위치를 알 수 있게 된다. 재귀호출을 사용하지 않은 Counting정렬을 사용해서 정렬을 마쳐도 메모리 초과가 생겼다.
※주의사항
1. Count배열에 사이즈를 정할 때, A배열의 MAX값보다 +1한 값으로 설정해야 한다. 인덱스 특성상 0부터 시작하므로.
<마지막>
배열 사이즈 최댓값이 10000000이라 int형 벡터나 배열을 선언할 경우 4*10000000byte= 40MB가 소요되므로 애시당초 입력값 전부를 담을 수 있는 최대크기 10000000짜리 배열을 만들 생각을 한것이 잘못이다. 배열에 들어가는 값의 최댓값은 10000이므로 카운팅배열 10000+1크기(인덱스고려)로 선언 후, 카운팅배열의 인덱스는 입력받은 값과 동일하다는 특징을 생각하여 코드를 짜보았다.
※주의사항
1. 메모리 초과는 전역변수가 힙에 들어간다고 해서 메모리 초과 범주에 안넣는 것이 아니다. 즉, 모든 변수와 함수의 메모리크기를 관리해야한다.
2. Counting정렬의 특징 : Count배열의 인덱스는 원본배열의 요소값, Count배열의 요소값은 정렬될 배열의 인덱스 혹은 원본배열 요소값 중복 수.
