글 읽기 - C) 메모리초과 질문드립니다.

swjo502 2년 전 0

예제를 돌려봤을 땐 제대로 나오는데

채점결과는 메모리 초과라고 나옵니다

어디가 문제인건가요? 범위들은 다 제대로 지정한거같은데

#include <stdio.h>

int list[10000001] = { 0, };
int arr[10000001] = { 0, };
int count[10001] = { 0, }, sum[10001] = { 0, };

int main() {
	int num;
	scanf("%d", &num);

	for (int i = 1; i <= num; i++) {
		scanf("%d", &list[i]);
		count[list[i]]++;
	}

	sum[0] = count[0];

	for (int i = 1; i <= 10000; i++) {
		sum[i] = sum[i - 1] + count[i];
	}

	for (int i = num; i >= 1;i--) {
		arr[sum[list[i]]] = list[i];
		sum[list[i]]--;
	}
	
	for (int i = 1; i <= num; i++) {
		printf("%d\n", arr[i]);
	}
}

euphoric_n 2년 전 0

list, arr가 각각 int 1000만개를 저장합니다.

int는 4바이트기 때문에 4 byte * 20000000 = 80000000 byte = 80MB이므로 당연히 메모리 초과에 걸리겠지요.

이 문제는 카운팅 소트를 사용하기 때문에 모든 수를 저장할 필요가 없습니다.

swjo502 2년 전 0

@euphoric_n 님 감사합니다.

배열 크기를 천만에서 10001로 줄이니 메모리 초과는 해결되었지만

이번엔 시간 초과가 뜨네요 ㅠ.ㅠ 코드를 아예 다시 짜야할까요?

euphoric_n 2년 전 0

고친 코드를 올려주세요.

swjo502 2년 전 0

@euphoric_n

배열의 길이만 수정했습니다!

#include <stdio.h>

int list[10001] = { 0, };
int arr[10001] = { 0, };
int count[10001] = { 0, }, sum[10001] = { 0, };

int main() {
	int num;
	scanf("%d", &num);

	for (int i = 1; i <= num; i++) {
		scanf("%d", &list[i]);
		count[list[i]]++;
	}

	sum[0] = count[0];

	for (int i = 1; i <= 10000; i++) {
		sum[i] = sum[i - 1] + count[i];
	}

	for (int i = num; i >= 1;i--) {
		arr[sum[list[i]]] = list[i];
		sum[list[i]]--;
	}
	
	for (int i = 1; i <= num; i++) {
		printf("%d\n", arr[i]);
	}
}

euphoric_n 2년 전 0

카운팅 소트 방식에 대해 설명 드리겠습니다.

카운팅 소트는 수의 입력 범위가 비교적 작고 입력 갯수가 많을 때 사용할 수 있는 정렬 방법입니다.

입력되는 수가 1 이상 10000 이하의 수이므로 10001개의 배열 크기를 가지는 count 배열을 선언하고 값을 0으로 초기화 합니다.

하나씩 입력받으면서 해당 입력 값을 인덱스로 하는 배열 값을 증가시킵니다.

이때 입력받는 값들은 배열 값을 증가시키는데만 사용되고 저장하지 않습니다.

입력이 끝나면 1부터 10000까지 모든 배열값을 확인하고 0이 아니라면 그 값만큼 반복해서 출력합니다.

list, arr, sum 전부 필요 없는 배열입니다. count 배열 하나면 됩니다.

swjo502 2년 전 0

@euphoric_n

감사합니다 ..!

말씀해주신 대로 다시 짜보겠습니다

다시 한 번 감사드립니다 한 번에 이해됐네요 ..!

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

문제

문제

출처

ICPC

C) 메모리초과 질문드립니다.

swjo502 2년 전 0

euphoric_n 2년 전 0

swjo502 2년 전 0

euphoric_n 2년 전 0

swjo502 2년 전 0

euphoric_n 2년 전 0

swjo502 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말