본문 바로가기
코딩과 알고리즘

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

728x90

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

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

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

과연 풀 수 있을까요?

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

 

10989번: 수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

www.acmicpc.net

입력되는 수는 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);

 

728x90
반응형