[BaekJoon]백준 4673번(셀프 넘버) 풀이 in python3

문제는 백준 사이트를 통해 확인해 보시길..

https://www.acmicpc.net/problem/4673

4673번: 셀프 넘버

 

 

1. 첫 번째 접근

# 1000*a + 100*b + 10*c + d
# def d(n):
#     a = n // 1000
#     b = n // 100
#     c = n // 10
#     d = n % 10
#     return 1001*a + 101*b + 11*c + 2*d <= 10000

처음 문제를 보고 셀프 넘버의 수학적 의미를 생각했을 때 d(n)함수를 위의 코드처럼 생각했다.

하지만 각 자리수로 접근 했을 때, 나중에 for loop를 적어도 4번 이상 사용할 가능성이 높아서 기본적인 빅오(O(n))가 높아진다고 생각했다.

코딩테스트의 특성 상 빅오를 최대한 낮출수록 통과할 확률이 높아지기 때문에 패스했다.

 

 

 

2. 두 번째 접근

# 함수 정의
def d(N):
    Ns = [int(i) for i in list(str(N))]  # 숫자 분해하기
    res = sum(Ns) + N					# d() 함수의 결과값 만들기
    return res							# 반환

# d(n)로 얻을 수 있는 모든 수
not_SelfNumList = [d(i) for i in range(10000) if d(i) <= 10000]

# SelfNumber 구하기
for r in range(10001):					# O(n)
    if r not in not_SelfNumList:		# check self number
        print(r)

먼저, d(n)함수에 대한 정의를 했다.

1) input인 n을 string으로 캐스팅한다.

2) string은 기본적으로 배열형식의 문자 조합임으로 이를 list에 담는다.

3) d(n)에 대한 결과값을 반환한다.

 

그 후, 10000 이하 수 중에서 Self Number가 아닌(== d(n)의 결과값) 수들의 리스트를 만든다.

이때, 코드를 좀 더 pythonic하게 코딩하기 위해 컴프리핸션(Comprehension)을 시도했다.

사실 반복값이 클수록 컴프리핸션의 성능은 떨어지지만 10000정도는 미미하다고 판단했다.

(컴프리헨션 성는에 관한 글 : [Tips] 컴프리헨션(Comprehension), 이터레이터(Iterator), 제너레이터(Generator))

 

마지막으로, not_SelfNumList에 포함되지 않는 수들의 집합으로 self Number를 찾아낸다.

 

 

 

 

 

채점 현황

시간 복잡도 측면에서 그렇게 뛰어난 성능은 아니지만 어쨌든 통과^^

개인적으로 가독성면에서는 괜찮은 코드라고 생각한다.