글 읽기 - 카운팅 소트에 short int로 해도 메모리초과라고 뜨네요

ostro57 8년 전 0

카운팅 소트로 해서 시간초과는 안나오는데요

이후에 메모리초과가 나와서

int대신 short int로 해도 메모리초과라고 뜨네요

어찌하면 좋을까요?

고수님들 도움 부탁드립니다.

#include <stdio.h>
#if 1
short int arr[1000000];
int x,y;

int N;
int nc;
short int cnt[10000];
short int tar[10000000];
#else


int arr[1000000];
int x,y;

int N;
int nc;
int cnt[10000];
int tar[10000000];
#endif

void main()
{
	int temp;
	scanf("%d",&N);

	for ( nc=0 ; nc< N; nc++)
	{
		scanf("%d",&arr[nc]);
	}

	for (x=0; x<N; x++)
		cnt[arr[x]]++;

	for ( x=1; x<=10000; x++)
		cnt[x]+=cnt[x-1];

	for ( x= N-1; x>=0; x--)
	{
		tar[cnt[arr[x]]]= arr[x];
		cnt[arr[x]]--;
	}
	for ( x=1; x<=N; x++)
		printf("%d\n",tar[x]);
}

pl0892029 8년 전 0

tar 배열이 없어도 풀 수 있지 않을까요?

gallopsys 8년 전 0

조금 다르게 생각해보면 arr 배열과 tar 배열을 쓰지 않고도 문제를 해결할 수 있습니다.

알고 계시겠지만, char 배열(1 Byte)로 천 만개를 할당한다고 해도 9MB를 약간 넘어버려서 메모리 초과가 뜨게 됩니다.

short int(short)형으로 위와 같이 할당하면 당연히 메모리 초과가 뜨겠지요..

이 문제는 문제의 조건에서 주어지는 수의 범위를 이용하시면 됩니다...!!

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

문제

문제

출처

ICPC

카운팅 소트에 short int로 해도 메모리초과라고 뜨네요

ostro57 8년 전 0

pl0892029 8년 전 0

gallopsys 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말