[Python] 코딩 도장 - 넥슨 입사문제

코딩 도장 사이트의 문제를 직접 풀어본 내용을 정리하여 올립니다.

코딩 도장에서 여러 문제를 확인할 수 있습니다.

난이도 순으로 차근차근 풀어보려 합니다.

---

[문제: 넥슨 입사문제] - Lv.1

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

출처: https://codingdojang.com/scode/365?answer_mode=hide

---

[풀이]

def d(n):
    return n + sum([int(i) for i in str(n)])

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

for n in range(2, 5001):
    for i in range(1, n):
        if d(i) == n:
            a[n].append(i)

lst = []
for i in a.keys():
    if sum(a[i]) == 0:
        lst.append(i)
        
print(sum(lst))

1227365

우선 d(n)을 정의하였고 제너레이터 n은 d(n)보다 클 수 없다.

즉, d(n)이 5이면 n은 5보다는 작아야 하므로 이를 이용해서 2부터 5000까지 각 숫자의 제너레이터를 구하였다.

각 숫자를 dictionary의 key로, 각 숫자의 제너레이터를 value로 생성하여 value의 합이 0인 self-number 리스트를 만들었다.

다만 이 방법은 반복이 너무 많아 수행 시간이 오래걸린다.

---

[추천 풀이]

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

1227365

이 풀이를 보고 느낀 것이 n < d(n) 임을 알았는데 왜 굳이 복잡하게 풀었나 싶다.

1부터 4999까지의 n과 d(n)을 생성해서 차집합으로 간단하게 풀어버렸다.

물론 내가 푼 방식은 각 숫자의 제너레이터가 무엇인지도 알 수 있지만 문제의 요점이 그게 아닌데 비효율적으로 구했다.