백준 알고리즘 10989. 수 정렬하기 3

백준 사이트 최백준씨의 재치가 돋보이는 문제입니다 :)

천만개의 수를 입력받고 정렬해서, 그 수를 순서대로 출력하시오! 라는 문제인데,

메모리 제한이 고작 8M입니다.

과연 풀 수 있을까요?

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

입력되는 수는 10,000 이하의 자연수입니다.

최소로 잡을 수 있는 타입은 int 형이고 int형은 2byte의 메모리 공간을 소모하지요.

10,000,000개의 숫자를 저장하려면 20,000,000 byte인데 그냥 저장만 하려고 해도 대략 20Mbyte의 공간이 필요합니다. 제공되는 메모리 제한 8M를 훌쩍 뛰어넘어버립니다.

​

"이거 문제가 잘못된게 아닌가요?" 라는 질문이 나올법도 하지만,

크레이는 30년차 개발자의 직감으로 한번에 느껴졌습니다 :)

​

만일 이 문제를 직접 풀어보시려 한다면 스포일러가 될 수 있으니 비법은 나중에 보도록 하시지요 

          :

          :

하지만, 이 게시글을 보고 계시다면 이미 해설을 보길 원하시는 거니 

말줄임표는 단 두 줄로 그치겠습니다 :)

​

우선 결론을 말씀드리면 이 문제는 정렬 문제가 아닙니다.

메모리 공간이 부족해서 천만개의 수를 저장하고 정렬할 수 없는데 해결책이 있다면

분명 다른 방법이 있는것이지요.

입력되는 수는 10000개의 자연수라는데에 그 힌트가 있습니다.

​

비법은 바로, 10000개의 공간을 미리 만들어 놓고 갯수를 0으로 초기화한 다음에,

1~10000까지의 수가 입력될 때마다 해당하는 순번의 공간의 갯수를 하나씩 증가시키는 겁니다.

​

예를 들어 아래와 같은 숫자가 순서대로 입력된다고 칩시다.

5 2 3 1 4 2 3 5 1 7

설명이니까 방은 10,000개 대신 7개만 미리 잡아둡니다.

그리고 모두 0으로 채워둡니다.

처음의 입력되는 숫자가 5이므로 5번째 칸의 숫자를 1 증가합니다.

두번째 숫자는 2인데 역시 2번쨰 숫자를 1 증가합니다.

이런 식으로 모든 숫자에 대해 해당 순번의 공간의 숫자를 1씩 증가합니다.

이제 정렬(?)은 끝났습니다.

"정말요?" 네!

첫번째 칸이 2개니까

1을 두번 출력합니다.

1
1

두번째, 세번째 칸도 2개니까 

2와 3을 각각 2번 출력합니다.

2
2
3
3

이런식으로 모두 횟수만큼 출력합니다.

대신 갯수가 0인 경우 출력하지 않습니다. 최종 결과입니다.

1
1
2
2
3
3
4
5
5
7

정렬같은건 하지 않았는데 마치 정렬한 것처럼 처리가 끝났습니다 :)

입력갯수가 최대 1개의 숫자만 몰아서 10,000.000개가 입력될 수 있기 때문에

long 형으로 10.000개의 빈공간을 잡아줄때 long 형은 4byte이므로 40,000byte, 즉 40Kbyte 면 대략 저장할 공간이 나옵니다.

메모리가 상당히 절약되었지요?

​

다만 이 방법은 입력되는 데이터가 1~10.000까지 범위가 작을 때 사용할 수 있는 방법입니다. 입력 데이터 범위가 크면 클수록 메모리 효율이 떨어지니 주의가 필요하지요 ㅎㅎ

​

소스 공개합니다~

#include <iostream>
#include <cstring>

void Result()
{
	long n, cnt;
	int tmp;
	scanf("%ld", &n);
	long *narr = new long[10001];
	memset(narr, 0, sizeof(int)*10001);
	for(long i=0;i<n;++i){	
		scanf("%d", &tmp);
		narr[tmp]++;
	}

	for(int i=1;i<=10000;++i){		
		char result[10];
		sprintf(result, "%d", i);
		cnt=narr[i];
		while(cnt--)puts(result);
	}
}

int main()
{
	Result();
}

부연설명입니다 :)

아래와 같은 부분이 있는데 여지껏 사용 안했던 방법이어서요.

​

이 문제는 동일한 수를 매우 많이 출력할 가능성이 있는데,

반복문에 printf 함수를 여러번 사용하면, 숫자를 "%d"에 넣는 분석과정에 시간이 많이 소요될 가능성이 있습니다.

그래서 먼저 result 에 한번만 쓰고

반복횟수만큼 문자열을 그대로 출력해주는 puts 함수를 사용하면 속도가 훨씬 빨라지지요.

참고로 puts 함수는 \n 개행문자를 기본으로 뒤에 출력해줍니다.

char result[10];
sprintf(result, "%d", i);
cnt=narr[i];
while(cnt--)puts(result);