넥슨 입사문제 중에서

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

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

47개의 풀이가 있습니다. 1 / 5 Page

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
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
    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;
}

이렇게 하면 되나염?

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

..

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

//1. self-number가 아닌 숫자를 찾아 리스트로 정리한다.
//2. 1 - 4999중 해당 리스트에 포함되지 않는 숫자를 전부 더한다.

public class Generator {
    //5000은 포함 하지 않는다
    private static final int LIMIT = 4999;

    //generator를 가지는 1 - LIMIT 범위 내의 숫자 목록
    private static ArrayList<Integer> notSelfNumberList;

    public static void main(String[] args) {
        initNotSelfNumberList();

        printTotalSelftNumberSum();
    }

    //not self-number list 셋팅
    public static void initNotSelfNumberList() {
        notSelfNumberList = new ArrayList<Integer>();

        //5000보다 작으며 5000에 가장 근접한 self값을 모르며 제한되는 generator를 모르기 때문에 LIMIT까지 진행.
        for (int i = 0; i <= LIMIT ; i++) {
            //해당 숫자를 generator로 가지는 값을 찾아 낸다.
            //찾아낸 수는 generator를 가지고 있으므로 notSelfNumberList에 포함 한다.
            //이때 생성된 수가 최초로 LIMIT값을 넘게 되는 순간 break(해당 숫자는 notSelfNumberList에 포함 안함)

            String strNum = String.valueOf(i);

            //자기 자신도 더해야 하므로 우선 자기 자신을 최초 숫자로 셋팅
            int notSelfNumber = i;
            //각 자리수를 전부 분해하여 더한다.
            for (int idx = 0; idx < strNum.length(); idx++) {
                notSelfNumber += Integer.parseInt(strNum.substring(idx, idx+1));
            }

            //더한 숫자가 한도 범위를 벗어 난다면 for문 중단.
            if (notSelfNumber > LIMIT) break;

            //한도를 넘지 않았다면 not self-number list에 포함
            notSelfNumberList.add(notSelfNumber);
        }
    }

    public static void printTotalSelftNumberSum() {
        int sum = 0;

        //1부터 LIMIT까지 진행
        for (int i = 1; i <= LIMIT; i++) {
            //not self-number list에 포함되어 있다면 통과
            if (notSelfNumberList.contains(i)) continue;

            //아니라면 최종합에 더하기.
            sum += i;
        }

        System.out.println("1 부터 " + LIMIT + "까지 self-number 가 아닌 모든 수의 합 : " + sum);
    }

}

결과는 1227365가 나오네요 ㅎㅎ
우연히 이곳을 알게 되었는데 많이 활성화 되면 좋겠습니다.
더불어 퀴즈도 많아지면 재미있겠네요

셀프넘버의 합계를 구하는거 아닌가요? cmd만 봐서는... - 김세연, 2014/02/28 10:46 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

ruby

([*1..5000] - (1..5000).map{|i| i.to_s.split("").map(&:to_i).reduce(:+)+i}).reduce(:+)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬으로 구현해 보았어요.

# -*- 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()
앗. 어려워....머리가 이제 점점 굳어지는.. - 조민영, 2011/08/18 10:08 M D
ㅎㅎ, 저도 이제 다시 풀라고 하면 못풀것 같아요. 이건 예전에 풀어보았던 거라서 ㅋㅋ - 길가의풀, 2011/08/18 10:09 M D
헉! 이게 뭐하는 짓이야? ㅠㅠ 머리아포...호~~ 해줘....ㅠ,.ㅜ - 한재수, 2011/08/19 18:22 M D
ㅋㅋ, 한번 풀어보세요, 치매예방됩니다. - 길가의풀, 2011/08/20 11:29 M D
유닛테스트 ㅋㅋㅋㅋㅋㅋ 위키찾아봐야겠당 - 유주성, 2011/10/18 09:48 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

아직 파이썬 배운지 얼마 안되서 별로 않좋은 코드를 짠것 같지만...많은 지적 부탁드립니다.

#NexonQuiz.py
#1부터 5000이하의 수중 generator가 없는 수들의 총합은?
import time
a=time.time()
genList=[]
for i in range(1,5000):
    genNumber=i
    for j in range(0,len(str(i))):
        genNumber+=int(str(i)[j])
    if (not genNumber in genList) and genNumber <=5000:
        genList.append(genNumber)

genSum=0
for j in range(1,5000):
    if not j in genList:
        genSum+=j

print('답은 {0} !!'.format(genSum))
print('걸린시간 : {0} 초'.format(time.time()-a))

코드에서 지적할 점이나 조언해주실 점 있으면 정말 감사하겠습니다ㅎ아직 초보라서..
읽어주셔서 감사합니다!ㅎ

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

bool check[5000];

void setD(int i)
{
    while(true)
    {
        int idx = i;
        int tmp = i;
        while(tmp)
        {
            idx+= tmp%10;
            tmp/=10;
        }
        if(idx < 5000 && check[idx]) check[idx] = false;
        else break;
    }
}
int main()
{
    fill_n(check,5000,true);
    for(int i=1;i<5000;i++) setD(i); //d(n) > n 이므로 5000까지만 체크해도 된다.
    long long sum=0;
    for(int i=1;i<5000;i++)
        if(check[i] == true)
            sum+=i;
    cout<<sum<<endl;
    return 0;
}

C스타일로 짜본 C++코드입니다. 재밌네요...!>

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

풀이 작성

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

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(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