넥슨 입사문제 중에서

어떤 자연수 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 보다 작은 모든 셀프 넘버들의 합을 구하라.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

308개의 풀이가 있습니다. 1 / 31 Page

위의 파이선코드들을 참조 했습니다.

sum(set(range(1, 5000)) - {x + sum([int(a) for a in str(x)]) for x in range(1, 5000)})

python 2.7.3

거의 예술이네요 - 엄마아빠아들입니다, 2014/08/14 18:37 M D
x에 91과 100이 들어가면 둘다 101이 앞의 sum에서 빼질텐데 어떻게 한번만 빼지는것이 되죠?? - 왈왈, 2016/07/08 19:05 M D
차집합이라 없으면 그냥 지나갑니다. - Flair Sizz, 2016/07/13 22:08 M D
울었다 .... - sega, 2016/08/22 18:45 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Python으로 작성해 보았습니다.

처음에 만든 코드는 아래와 같았습니다.

def d_fn(n):
    y = n
    while n > 0:
        y += n % 10
        n //= 10
    return y

Z = [d_fn(n) for n in range(5000)]
A = [n for n in range(5000) if n not in Z]
print (sum(A))

그 다음에는 문자열을 사용해서 조금 더 짧게 고쳐봤습니다.

def d_fn(n): return (n + sum([int(x) for x in str(n)]))

Z = [d_fn(n) for n in range(5000)]
A = [n for n in range(5000) if n not in Z]
print (sum(A))

여기에 아래와 같이 집합 데이터 구조를 사용해 보니 더 직관적으로 고쳐지는 것 같습니다.

def d_fn(n): return (n + sum([int(x) for x in str(n)]))

S = set(range(5000))
Z = set([d_fn(n) for n in range(5000)])
print (sum(S-Z))
와.. 깔끔한 파이썬코드, 언제나 반갑네요 ^^ - 길가의풀, 2012/06/19 16:24 M D
저는 1줄짜리 파이썬 코드가 예술로 보이긴하지만 가독성을 높이기는 이게 더 좋은 것 같습니다. 추천주고 갑니다 - 전영배, 2015/06/12 02:19 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
public static void main(String[] args)
    {
        calculateNumbersHasGenerator();
        int sum = 0;
        for (int i = 0; i < 5001; i++)
            if (!hasGenerator(i))
                sum += i;
        System.out.println("합 : "+sum);
    }

    private static boolean hasGenerator(int num)
    {
        return numbersHasGenerator.contains(num);
    }

    private static ArrayList<Integer> numbersHasGenerator;

    private static void calculateNumbersHasGenerator()
    {
        numbersHasGenerator = new ArrayList<Integer>();
        for (int i = 0; i <= 5000; i++)
        {
            String num = String.valueOf(i);
            int no = 0;
            for (int n = 0; n < num.length(); n++)
                no += Integer.parseInt(num.substring(n, n + 1));
            numbersHasGenerator.add(no + i);
        }
    }

합 : 1227365

자바로 짯습니다. 코딩 퀴즈 재밌군요. 아직 많이 부족한 실력이라, 적극적인 지적 환영합니다.

+1 for (int i = 0; i < 5001; i++) 여기서 5000 이 맞겠군요. 5000 보자 작은 숫자이니.. 문제를 잘못봐서.. - 이학수, 2012/02/04 17:50 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬 3.2.5 기준입니다.

def d(number):
    total = number
    number = str(number)
    for i in number:
        total += int(i)
    return total

self_number_total = 0
self_number_set = set()

for i in range(1,5000):
    self_number_set.add(d(i))

for i in range(1,5000):
    if not i in self_number_set:
        self_number_total += i

print(self_number_total)

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬의 def를 사용하지 않고 set() 의 차집합을 이용해서 작성해보았습니다.

nums = range(1,5001)
selfnums = set(nums) - set([sum([int(ii) for ii in str(num)]) + num for num in nums])

print sum(selfnums)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

J를 이리 저리 익혀 보려고 하고 있는데 손에 잘 안 익네요. 그래도 일단 풀긴 풀었습니다. 그다지 깔끔한 것 같지 않은데 J 하시는 분들의 가멸찬 지적 바랍니다...

   +/I.-.(e.(++/"1@(10&#.^:_1)))i.5001
1227365

처음부터 이렇게 만들었다는 소리는 아니고요, 대강 이렇게 구성됩니다.

   digits =: #.^:_1
   digits10 =: 10 & digits
   digits10 4057 2289
4 0 5 7
2 2 8 9

J에 내장되어 있는 #.(base)라는 함수는 오른쪽의 인자들을 2진법(또는 왼쪽 인자가 있으면 그 진법)으로 해석해서 하나의 숫자로 만듭니다. 이를테면 "#. 1 1 0 1"은 13이 되겠죠. ^:_1는 함수의 의미를 뒤집는 역할을 합니다.

   +/ digits10 4057 2289
6 2 13 16
   +/"1 digits10 4057 2289
16 21

J에서 배열의 합을 구할 때는 흔히 +/(sum)을 씁니다만 이 경우 오른쪽 인자가 여럿일 때도 동작해야 하기 때문에 행과 열을 잘 생각해야 합니다. +/(좀 더 정확히는, /)의 기본값은 열 별로 더하는 것이므로 이 동작을 바꾸려면 "1로 rank를 바꿔 줘야 합니다.

   digitsum =: +/"1 @ digits10
   d =: + digitsum
   d 2289
2310

고로 digitsum은 오른쪽 인자를 10진법 자릿수로 나눈(digits10) 것을 행 별로 다 더한(+/"1) 것으로 정의할 수 있습니다. 함수 d(x)는 당연히 x + digitsum(x)로 정의되는데, J의 fork를 사용하면 코드가 좀 더 간단해집니다. 사실 이렇게 안 하면 괜시리 복잡해지기도 하고요.

   i.20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
   d i.20
0 2 4 6 8 10 12 14 16 18 11 13 15 17 19 21 23 25 27 29

이제 앞에서 정의했던 d를 가지고 self number의 목록을 구합니다. i.(integers)는 0부터 주어진 인자 빼기 1까지를 담은 배열을 만들고(파이썬의 range와 거의 비슷합니다), 앞에서도 살펴 봤지만 배열에 함수를 적용하면 배열 각 원소에 함수가 모두 자동으로 적용됩니다. (+/와 같이 다른 형태로 동작하는 경우도 물론 있습니다.)

   (i.20) e. (d i.20)
1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1
   (e. d) i.20
1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1

e.(member)를 써서 집합 빼기(set difference) 비스무리한 걸 구현할 수 있습니다. (d에 ^:_1을 적용할 수 있으면 참 좋겠지만 d의 역함수는 애초에 함수가 아닙니다...) 앞에서 fork 얘기를 했는데 여기서도 한 번 더 쓰게 되네요.

   -. (e. d) i.20 
0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
   I. -. (e. d) i.100
1 3 5 7 9 20 31 42 53 64 75 86 97
   +/ I. -. (e. d) i.5001
1227365

-.(not)을 써서 0과 1을 뒤집은 뒤, I.(indices)를 써서 1이 있는 칸의 인덱스만 빼 오면 d의 반환값에 나오지 않았던 모든 숫자들을 구할 수 있습니다. 그 결과를 모두 더하면(이번에는 그냥 +/로) 결과를 얻을 수 있습니다. 맨 위의 코드는 이 코드에서 공백 떼고 d를 안에 넣어서 완성한 것입니다.

지금 보니까 #.(base)의 반대 되는 역할을 하는 #:(antibase)가 이미 내장으로 있었네요. Vocabulary를 아무리 봐도 헷갈리는 듯... - 아라크넹, 2012/02/05 00:52 M D
-1 놀라울 따름입니다. 친절히 해석도 달아주셨으니 시간내서 공부좀 해 봐야 겠네요 ^^ - 길가의풀, 2012/02/05 14:49 M D
-1 J 실력이 지금보다 좀 미천했을 때 푼 방식입니다: http://agile.egloos.com/1718200 - 김창준, 2012/03/04 22:35 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
import math
def d(x):
    x=str(x)
    s=int(x)
    for i in x:
        s+=int(i)
    return s
s=0
i=1
a=d(i)
while a<5000:
    s+=a
    i+=1;a=d(i)


print((4999*5000/2)-s)

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
    Sub Main()
        Dim result As Integer = 0
        Dim ht As New Hashtable

        For i As Integer = 1 To 4999
            Dim n As Integer = GetGenerator(i)

            If n < 5000 Then
                ht.Add(i, n)
            End If
        Next

        For i As Integer = 1 To 4999
            If Not ht.ContainsValue(i) Then
                result += i
            End If
        Next

        Console.WriteLine("Result: " & result)

        Console.ReadLine()
    End Sub

    Public Function GetGenerator(n As Integer) As Integer
        Return n + (From str In n.ToString.ToArray Select Integer.Parse(str)).ToArray.Sum
    End Function

1227365

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#include <iostream>

using namespace std;

static const int N = 5000;

int d(int n)
{
  int res = n;
  while (n != 0) { res += n % 10; n /= 10; }
  return res;
}

int main()
{
  bool isSelfNo[N + 1];
  for (int i = 0; i <= N; i++) isSelfNo[i] = true;
  int sumOfSelfNo = 0;
  int n = 1;
  while (n <= N)
  {
    if (isSelfNo[n]) sumOfSelfNo += n;
    int _d = d(n);
    if (_d <= N) isSelfNo[_d] = false;
    n++;
  }
  cout << sumOfSelfNo << endl;
}

이렇게 하면 되나염?

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

코딩도장 자주 애용할 듯 합니다ㅎㅎ 자바에요

public class SelfNumber {

    public static void main(String[] args) {
        // 1~5000 까지
        // generator 로 돌려서 각 값을 배열에 저장
        // 그중 1~5000과 일치하지 않는 수를 골라낸다
        // int 를 나눌 경우 소수점 이하는 계산에서 무시되므로 int를 사용

        Integer a,b,c,d,result,sum=0;

        boolean[] generated = new boolean[5000];

        for(int generator=1; generator<5000;generator++){
            a = generator/1000;
            b = (generator/100)%10;
            c = (generator/10)%10;
            d = generator%10;

            result = a+b+c+d+generator;

            if((result>=1)&&(result<5000)){
                generated[result] = true;
            }
        }

        for(int i=1; i<5000; i++){
            if(generated[i]==false){
                sum = sum + i;
            }
        }

        System.out.println("Self-Number의 합계는 : " + sum);

    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 308
erlang x 1
haskell x 2
clojure x 2
java x 56
scala x 8
python x 100
delphi x 3
javascript x 4
r x 2
perl x 1
cpp x 49
기 타 x 47
matlab x 4
cs x 11
lisp x 2
objectivec x 4
php x 6
ruby x 6