[Algorithm] 백준 알고리즘 셀프넘버

https://www.acmicpc.net/status?user_id=seophaa&problem_id=4673&from_mine=1

채점 현황

 

---

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력은 없다.

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

 

 

 

 

---

- C#

 

접근방식

1. boolean arr[10001] 하나 생성후, 모두 true값 넣어주기 2. 배열의index를 1~10000까지의 숫자로 생각하고 셀프 넘버 판별 함수 생성  3. 판별 함수는 해당 index의 값을 string으로 받아 substring을 이용해 해당 숫자를 받아오게 하였다 4. 셀프 넘버 판별 함수에서 나온 결과 값을 boolean arr[10001]의 해당 index값으로 생각하고    해당 인덱스 값에 false 값 넣어주기 5. boolean arr[10001]에서 true 값을 가진 index 출력

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace test19
{
    class Program
    {
        static void Main(string[] args)
        {
            Program pg = new Program();
 
            bool[] arr = new bool[10001];
            arr = arr.Select(s => s = true).ToArray();
 
            for (int i = 0; i < arr.Length - 1; i++)
            {
                if (pg.Calc(i + 1) > (arr.Length - 1)) continue;
                arr[pg.Calc(i + 1)] = false;
            }
 
            for (int i = 1; i < arr.Length - 1; i++)
            {
                if (arr[i] == true)
                    Console.WriteLine(i);
            }
        }
        private int Calc(int number)
        {
            var result = new List<int>();
            int tmp = 0;
            result.Add(number);
 
            for (int i = 0; i < number.ToString().Length; i++)
            {
                tmp = int.Parse(number.ToString().Substring(i, 1));
                result.Add(tmp);
            }
            return result.Sum();
        }
    }
}
 

- Python

 

접근방식

1. list[10001] 모두 0을 넣어 생성 2. 배열의 index를 1~10000까지의 숫자로 생각하고 셀프 넘버 판별 함수 생성  4. 판별 함수는 해당 index의 값을 string으로 받아 string의 index를 이용해 해당 숫자를 받아오게 하였다 5. 셀프 넘버 판별 함수에서 나온 결과 값을 booleam arr[10001]의 해당 index값으로 생각하고    해당 인덱스 값에 '1' 넣어주기 6. list[10001]에서 0의 값을 index 출력

def calc(a):
 
    b = list()
    
    for v in range(0,len(str(a))):
        b.append(int(str(a)[v:v + 1]))
 
    num = sum(b) + a    
    return num
 
 
lst = [0 for _ in range(10001)]
for i in range(10001):
    a = calc(i)
    if a >= 10001: continue
    lst[a] = 1
 
for i in range(10001):
    if lst[i] == 0:
        print(i)

 

 

---

 

 

 셀프 넘버를 판별하는 것 보다는 셀프넘버가 아닌것을 찾는 방식으로 접근했다.

1~ 10000까지의 숫자를 따로 구하는 것이 아니라 필요한 숫자의 크기만큼 배열을 미리 선언하여

index를 사용하여 해당되는 배열을 false나 1의 숫자로 바꿔 주었다. 위와 같은 방식으로 구하면 true나 0으로 되어있는

수들이 모두 셀프 넘버라 할수있다.

 

셀프넘버 판별 함수는 index값을 string으로 받아 C#은 subString, Python은 string의 index값을 받게 한 후 list에 저장해 계산하도록 하였다.

 

그리고 10000이상의 값이 나오는 경우에는 continue를 하였다.