글 읽기 - (C) 메모리초과... 카운팅소트

kwkimg3100 6년 전 0

초기에는 그냥 10000으로 잡아서 코딩했는대 이게 되긴되지만 메모리가... 그래서 calloc으로 구현했습니다.

그런대도 메모리 초과이네요... 어디서 메모리를 더 줄일수있을까요?

#include <stdio.h>
#include <stdlib.h>

int main() {
	int a, b, d, e;
	scanf("%d", &a);                      //몇개의수를 입력받을건지 정함
	int p = 0;
	int *arr = calloc(a, sizeof(int));  
	int *place = calloc(a, sizeof(int)); 
	if (1 <= a <= 1000000) {
		for (b = 0; b < a; b++) {
			scanf("%d", &arr[b]);         //정렬할 숫자들
			if (p <= arr[b]) {                 
				p = arr[b];
			}
		}
	}
	else {
		return 0;
	}
	int *index = calloc(p, sizeof(int));         //입력받은숫자들중 가장큰수만큼 동적할당
	for (b = 0; b < a; b++) {
		index[arr[b]-1] += 1;                    //그후 카운팅
	}
	for (d = 0; d < p; d++) {
		index[d+1] = index[d] + index[d + 1];    //카운팅들을 차례로 더함
	}
	for (e = 0; e < a; e++) {
		int p = arr[e];
		int q = index[p-1];                      //정렬
		place[q] = arr[e];
		index[p-1] -= 1;
	}
	for (e = 0; e < a; e++) {
		printf("%d ", place[e+1]);
	}
}

djm03178 6년 전 0

모든 입력을 배열에 저장하지 말고 나온 횟수만 저장하세요.

jh05013 6년 전 0

그리고 입력 범위를 다시 보세요. 애초에 10줄의 if문은 필요 없습니다. 입력 조건을 코드에 넣지 않아도 됩니다.

kwkimg3100 6년 전 0

카운팅소트인대 입력받은 숫자들 저장해두어야 나중에 정렬할수있지않나요??

djm03178 6년 전 0

저도 학부 수업에선 그런 식으로 배웠지만, 더 간단하고 쉽게 하는 방법이 있습니다.

jh05013 6년 전 0

"정렬"을 한다는 것부터 데이터를 저장해야 하는 것으로 볼 수 있긴 하지만, 정렬된 결과를 출력하는 것은 데이터를 저장하지 않아도 할 수 있습니다.

chogahui05 6년 전 1

카운팅 소트라는 게.. s라는 수가 얼마만큼 나왔는지 저장하면 써먹을 수 있어요. 이 문제 같은 경우 나오는 인풋 양에 비해

수 범위가 상당히 작기 때문에 쓸 수 있고요.

예를 들어서 1 2 3 1 이렇게 나왔으면

1은 2번 등장.

2는 1번

3도 1번 등장.

이런 식으로 저장하면 나중에 출력할 때 1은 2번 등장했으니까

1 1

다음에 2는 1번 등장했으니

2

담에 3은 1번 등장했기 때문에

3

이래 출력하면 될 거 같아요.

kwkimg3100 6년 전 0

감사합니다ㅎㅎ

sayoo21 5년 전 0

카운팅소트의 정의가아닌 단순 10000개까지의 숫자의개수 출력이라 메모리 크기가8MB여도 충분하다니! 오늘도 한 수 배우고 갑니다.

댓글을 작성하려면 로그인해야 합니다.