넥슨 입사문제 중에서

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

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

15개의 풀이가 있습니다. 1 / 2 Page

        static void Main(string[] args)
        {
            Hashtable hst = new Hashtable();
            int Sum = 0;

            for (int i = 0; i < 5000; i++)
            {
                int tmp = jene(i);
                if (tmp < 5000)
                {
                    hst.Add(i,tmp);
                } 
            }

            for (int i = 0; i < 5000; i++)
            {
                if (!hst.ContainsValue(i))
                {
                    Sum += i;
                }
            }

            Console.WriteLine(Sum);
        }

        public static int jene(int Ine)
        {
            int result = 0;   

            string Tmp = Ine.ToString();


            int[] TmI = new int[Tmp.Length];


            for (int i = 0; i < Tmp.Length; i++)
            {
                TmI[i] = Convert.ToInt32(Tmp[i].ToString());
            }

            result += Ine;

            for (int i = 0; i < TmI.Length; i++)
            {
                result += TmI[i];
            }

            return result;
        }
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
//유니티 C#으로 도전해봤어요. 실력이 워낙 없어서 좀 지저분합니다. ^^ 의지의 한국인 정도로 생각해주세요~

using UnityEngine;
using System.Collections;

public class NexonQuiz {

    // Use this for initialization
    void Start () {
        int[] array = new int[5000];
        for(int i = 1; i < 5000; i++){
            int gene = getGenerator(i);
            if( gene < 5000 )
                array[gene] = gene;
        }

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

        Debug.Log( sum ); // 정답: 1227365
    }

        //제너레이터 구하기
    private int getGenerator(int integer){
        int chpher = getCipher(integer);
        int[] array = new int[chpher];

        int nTemp = integer;
        for(int i = 0; i < chpher; i++){
            array[i] = nTemp % 10;
            nTemp = nTemp / 10;
        }
        int sum = 0;
        for(int i = 0; i < chpher; i++){
            sum += array[i];
        }

        return sum + integer;
    }

        //자릿수 구하기
    private int getCipher(int integer){
        int count = 0;
        int nCheck = 1;
        while( integer / nCheck > 0 ){
            nCheck *= 10;
            count ++;
        }

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

class Program
{
    static void Main()
    {
        var sumOfSelfNumbers = 0;
        var generatedNumbers = new List<int>();

        for (var i = 1; i < 5000; i++)
        {
            if (generatedNumbers.Contains(i) == false)
            {
                sumOfSelfNumbers += i;
            }
            generatedNumbers.Add(d(i));
        }

        Console.WriteLine("sumOfSelfNumbers = " + sumOfSelfNumbers);
    }

    static int d(int number)
    {
        var generate = number;
        var digits = number.ToString().ToCharArray();

        foreach (var aDigit in digits)
        {
            generate += Int32.Parse(aDigit.ToString());
        }

        return generate;
    }
}

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

C#으로 재귀함수를 이용해서 작성해 보았습니다.

        private void button1_Click(object sender, EventArgs e)
        {
            List<int> sumArray = new List<int>();
            for (int i = 1; i <= 5000; i++)
            {
                sumArray.Add(sumDigits(i) + i);
            }
            int sum = 0;
            for(int i = 1; i <= 5000; i++)
            {
                bool isIn = sumArray.Contains(i);
                if(!isIn) sum += i;
            }
            Console.WriteLine(sum.ToString());
        }
        private int sumDigits(int number)
        {
            int perTen = number / 10;
            if (perTen == 0) return number;
            else return number - perTen * 10 + sumDigits(perTen);
        }

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

namespace selfNumber
{
    class Program
    {
        static void Main(string[] args)
        {   
            int nMaxArray = 5000;       // 1 ~ 어떤숫자까지 체크 할것인가(자연수)
            int nMaxCheckValue = 5000;  // 루프돌면서 체크할 숫자의 Max값

            bool[] arIsNotSelfNumber = new bool[nMaxArray];
            for (int nCnt = 1; nCnt <= nMaxCheckValue; nCnt++)
            {
                int nGenResult = getGenerator(nCnt);    // while루프함수 버전

                if (nGenResult - 1 < nMaxArray)
                {
                    arIsNotSelfNumber[nGenResult - 1] = true;
                }
            }

            int nSumNaturalNum = 0;
            for (int nCnt = 1; nCnt <= nMaxArray; nCnt++)
            {
                if (arIsNotSelfNumber[nCnt - 1] == false)
                {
                    nSumNaturalNum += nCnt;
                }
            }


            System.Diagnostics.Debug.Print("1 ~ " + nMaxArray + " 까지의 셀프넘버의 합은 : " + nSumNaturalNum);

        }

        static int getGenerator(int nValue)
        {
            int nResult = 0;
            nResult += nValue;

            int nCopiedValue = nValue;
            bool bLoop = true;
            while (bLoop)
            {
                if (nCopiedValue / 10 != 0)
                {
                    nResult += nCopiedValue % 10;
                    nCopiedValue /= 10;
                    bLoop = true;
                }
                else
                {
                    nResult += nCopiedValue;
                    bLoop = false;
                }

            }

            return nResult;
        }

    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
const int MAX = 5000;
bool[] isdn = new bool[MAX];
int t = 0, dn = 0, sum = 0;

for (int i = 0; i < MAX; t = dn = i++)
{
    do dn += t % 10;
    while ((t /= 10) >= 1);

    if (dn < MAX) isdn[dn] = true;
    if (!isdn[i]) sum += i;
}

C#으로 작성하였습니다. 순차적인 정수배열이 필요없는 인덱스 방식을 생각해보았습니다. 그리고 셀프넘버는 룹을 돌며 나오는 d(n)보다 항상 작으므로 하나의 for문으로도 간단히 처리할 수 있었습니다. 1000만개를 돌렸을때, 약 0.6초의 계산시간이 소요되었습니다.

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

C#

List<int> srcAry = Enumerable.Range(1, 5000 - 1).ToList();

// 제네레이터값들 획득
var noSelfNums = srcAry.Select(_v => _v.ToString().ToCharArray().Select(_c => _c - 48).Sum() + _v).ToList();

// 셀프넘버 획득
srcAry.RemoveAll(_v => noSelfNums.IndexOf(_v) >= 0);

// 합 출력
Console.WriteLine(srcAry.Sum());

-Output-------
1227365

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

C#으로 작성했습니다. Hashtable을 사용했습니다.

using System.Collections;

        public int SumOfSelfNumbers(int n)
        {
            var sum = 0;
            var outputs = new Hashtable();
            for (int i = 1; i < n; i++)
            {
                var d = i/1000 + (i%1000)/100 + (i%100)/10 + i%10 + i;
                outputs[d] = i;
            }
            for (int i = 1; i <= n; i++) sum += outputs.ContainsKey(i) ? 0 : i;
            return sum;
        }
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
static void Main(string[] args)
{
    List<int> list      = new List<int>();
    List<int> self_list = new List<int>();
    for (int i = 1; i <= 5000; i++)
    {
        list.Add(i);
        self_list.Add(i);
    }

    foreach(int x in list)
    {
        var gen = Generator(x);
        if (list.Contains(gen))
            self_list.Remove(gen);
    }

    var sum = self_list.Sum();

    Console.WriteLine(sum);
}

static int Generator(int x)
{
    string[] value = x.ToString().ToCharArray().Select(z => Convert.ToString(z)).ToArray();

    int result = 0;
    for (int i=0; i< value.Length; i++)
    {
        if(!string.IsNullOrEmpty(value[i]))
        {
            result += Convert.ToInt32(value[i]);
        }
    }

    return (result += x);
}

숫자를 문자배열로 바꿔서 더하고, 제너레이트인것들을 리스트에서 제외하고 합을 구해봤습니다. 어렵네요.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
Stopwatch sw = Stopwatch.StartNew();
int SIZE = 4999;
Func<int, int> generator = (n) => (n.ToString().Sum(k => Convert.ToInt32(k.ToString()))) + n;
int[] nonselfnum = Enumerable.Range(1, SIZE).Select(k => generator(k)).Distinct().ToArray();
int selfnumSum = Enumerable.Range(1, SIZE).Where(k => !nonselfnum.Contains(k)).Sum();
sw.Stop();
Console.WriteLine($"Elapsed MillSecond : {sw.ElapsedMilliseconds}, Value : {selfnumSum}");

Elapsed MillSecond : 24, Value : 1227365

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

풀이 작성

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

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


언어별 풀이 현황
전 체 x 364
python x 119
기 타 x 58
java x 67
matlab x 5
scala x 8
cs x 15
cpp x 56
php x 6
delphi x 3
ruby x 6
haskell x 2
lisp x 2
javascript x 5
r x 2
clojure x 2
erlang x 1
perl x 1
objectivec x 5
go x 1