셀프넘버 (Self Number)

넥슨 입사 문제로 유명했던 셀프넘버 구하기 문제



어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자.

예를 들어 d(91) = 9 + 1 + 91 = 101

이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다.

어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.

1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.

---> 자기 자신을 어잡히 더하기 때문에 5000보다 큰 숫자는 구해볼 필요가 없다. 

---

C언어로 작성 해본 것

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define MAX_NUMBER		5000

int Generator(int number);

int main(void)
{
	int sum = 0;
	bool selfNumber[MAX_NUMBER + 1];
	memset(selfNumber, true, sizeof(selfNumber));

	for( int i = 1 ; i <= MAX_NUMBER ; i++ )
	{
		int generator = Generator(i);

		if( generator <= MAX_NUMBER ) // 셀프넘버 아님
			selfNumber[generator] = false;
	}

	for( int i = 1 ; i <= MAX_NUMBER ; i++ )
	{
		if( selfNumber[i] == true )
		{
//			printf("Self-Number found !!! : %d\n", i);
			sum += i;
		}
	}

	printf("Sum of Self-Number = %d\n", sum);

	return 0;
}

int Generator(int number)
{
	int total = 0;
	int  mod;

	total += number; // 일단 자신을 더한다.

	while(number>0) // 자릿 수를 줄여가면서 첫번째 자리를 더한다.
	{
		mod = number % 10;
		number = number / 10;
		total = total + mod;
	}
	

	return total;
}

파이썬으로 작성한것 1 ( http://wikidocs.net/read/735 )
C언어로 작성한것보단 약간 느리다 .

# -*- coding: euc-kr -*-
import unittest
 
def add_digit(no):
    return sum(map(int, ' '.join(str(no)).split()))
 
def f(no):
    return add_digit(no)+no

refer = {}
for i in range(1, 5001): refer[i] = f(i)

def getgen(no):
    result = []
    for n in range(1, no+1):
        #if f(n) == no: result.append(n)
        if refer[n] == no: result.append(n)
    return result

def selfno(limit):
    result = []
    for i in range(1, limit+1):
        if not getgen(i): result.append(i)
    return result


class GeneratorTest(unittest.TestCase):
    def test1(self):
        self.assertEquals(2, add_digit(200))
        self.assertEquals(10, add_digit(91))
        self.assertEquals(101, f(91))
        self.assertEquals(101, f(100))
        self.assertEquals([1], getgen(2))
        self.assertEquals([91, 100], getgen(101))
        self.assertEquals([1,3,5,7,9], selfno(10))
        print "result:", sum(selfno(5000))

if __name__ == "__main__":
    unittest.main()

파이썬으로 작성한것 2 ( http://wikidocs.net/read/735 )
-> 파이썬에는 is_self_generator 란것이 있나보다... 근데 굉장히 느리다.. 

def is_self_generator(n):
    for i in range(1,n):
        a = 0
        for j in str(i):
            a += int(j)
        a += i
        if a == n:
            return False
    return True

s = 0
for i in range(1,5000):
    if is_self_generator(i):
        s += i
print s