백준4673 셀프넘버 using Python

열어보며

1부터 10001 사이의 Self Number를 구하는 문제이다.

• Self Number란?
  d(n) 이라는 함수가 존재하고, 이 함수는 n + n의 각 자리수들을 총합하여 반환한다고 할 때, d(n)에 어떠한 값을 입력해도 output으로 그 수가 나올 수 없는, 즉 생성자가 없는, 값을 뜻한다.

첫번째 구상 및 문제 봉착

일단 처음 고민했던 방법으로는 두 사용자 함수를 정의하여 풀어내는 방식이었고, 두 함수는 아래와 같다.

• function1 : 문제에서 제시된 d(n)을 그대로 구현하여 그 리스트를 저장하는 함수

• function2 : 자연수 1에서 10001사이의 값에서 d(n)의 출력 리스트의 원소들을 제외한 결과 리스트를 구하고, 이 리스트 원소를 순서대로 출력해내는 함수

아래는 위의 함수들을 구현해본 지저분했던 첫번째 코드의 일부이다.

• 문제1 : function1인 d(n) 함수를 구현하며 생각보다 비효율적이고 지저분하다는 느낌을 받았다. 분명 훨씬 나은 short-cut 을 만들어 낼 수 있다고 생각했지만, 어쨌든 function 1은 구현했고 정상적으로 동작했다.

• 문제 2 : critical한 문제에 봉착했다. 두 list간의 중복원소를 어떻게 제외시킬지에 대한 고민이었다. 결국 항복선언하고 방법을 탐색해봤는데 조금 허탈한 기분을 느꼈다.

  아는 것이 힘이라는 교훈을 다시한번 가슴깊이 새긴다.

  • 문제 2의 해결방법은 간단했다.
    list가 아닌 set자료형을 비교해내면 되는 문제였다.

    난 이를 반복으로 한땀한땀 구현하고자 했는데

    Nested Loop를 사용하자니 10001x10001의 비효율적인 비교과정을 거치기 때문에 비효율적이기도 하며, 정작 이를 구현하는것도 만만치 않았다.

    그리고 결국 항복을 선언하고 function2를 대체할 방법을 찾았고 set간의 연산을 이용하면 직접 함수를 구현할 필요 없이 간단하게 해결할 수 있음을 알아냈다.

    ( 물론 리스트도 가능할 지 모르겠으나, 이는 차차 알아갈 문제이다 )

set1 - set2 를 실시하면 집합간 빼기연산으로 set1에서 set2에 존재하는 동일원소를 제거한 결과 집합을 반환하는 아주 간단한 방법으로 function2를 대체했다.

최종코드

function1도 더 효율적인 short-cut을 참조하여 다듬었다.

• 기존 방법에선 str으로 list를 따로 저장해두었는데, 현 코드에선 비효율을 줄여 str하여 list로 만든 문자리스트를 그대로 level-2 Loop의 반복리스트로 사용했다.

그리고 불필요한 함수정의 또한 사용하지 않기로 했다.

naturalNum = set(range(1,10001))
compareNum = set()

#function1에 해당하는 부분
for i in range(1,10001):
  sum = 0
  for j in str(i) :
    sum += int(j)
  sum += int(i)
  
  compareNum.add(sum)
  
#function2에 해당하는 부분
selfNum = sorted(naturalNum - compareNum)

for i in selfNum :
  print(i) 

ref
https://wook-2124.tistory.com/252