인공지능 개발일지

[백준 알고리즘 4673] 셀프 넘버 (Python) 본문

개발 지식/알고리즘

[백준 알고리즘 4673] 셀프 넘버 (Python)

Prcnsi 2022. 5. 26. 16:23
728x90

 

문제

문제는 1~10000까지의 정수 중에서 셀프 넘버를 출력하는 것이다. 셀프 넘버는 생성자가 없는 숫자이다.
생성자는 함수 d(n)에서 나오는데 d(n)은 각각 자리를 더해 다음 수를 만드는 것으로 아래 예시와 같이 다음 수를 만든다.

  • 33 + 3 + 3 = 39
  • 39 + 3 + 9 = 51
  • 51 + 5 + 1 = 57


그래서 다음 수를 만드는 수 33, 39, 51과 같은 수를 생성자라고 한다. 그래서 셀프 넘버는 1~10000 중에서 생성자가 없는 수를 말한다.

  • 입력: X
  • 출력: 셀프 넘버

 

풀이

그래서 풀이는 전체 1~10000까지의 전체 집합과 지울 생성자 집합을 만들고 셀프 넘버를 생성하고 그 값을 생성자 집합에 넣어서 저장하고 이후에 전체 집합에서 생성자를 제외하고 정렬해서 출력하면 된다.
그래서 여기서 이용한 아이디어는 전체 집합을 만들고 생성자 집합을 빼는 것이다.

나는 처음에 생성자를 만들고 나중에 10000의 반복문에서 하나하나 생성자인지 검사해서 출력하려고 했는데 위 방법이 더 효율적인 것 같다.

코드

# 전체 숫자 집합 생성
numbers=set(range(1,10000))
remove_set=set()

# 생성자인 숫자 remove_set에 담기
for num in numbers:
    for n in str(num):
        num+=int(n)
    remove_set.add(num)

# 전체 숫자에서 remove_set 지우고 정렬해서 출력
self_numbers=numbers-remove_set
for self_num in sorted(self_numbers):
    print(self_num)
728x90