이 글에서는 주어진 숫자 n이 행복한 숫자(Happy Number)인지 아닌지를 파이썬으로 판별하는 방법을 알아보겠습니다.
행복한 숫자란?
행복한 숫자는 다음과 같은 성질을 가진 수입니다. 임의의 양의 정수에서 시작하여 그 숫자를 각 자릿수의 제곱의 합으로 계속 바꾸어 나갈 때, 최종적으로 1에 도달하면 그 수는 행복한 숫자입니다. 반대로 1에 도달하지 못하고 같은 사이클을 무한히 반복하게 되면 행복한 숫자가 아닙니다.
예시: 19
숫자 19를 예로 들어 보겠습니다. 19는 행복한 숫자이므로 결과는 True가 됩니다.
- 12 + 92 = 82
- 82 + 22 = 68
- 62 + 82 = 100
- 12 + 02 + 02 = 1
이처럼 과정을 반복했을 때 1에 도달하므로 19는 행복한 숫자입니다.
해결 접근 방식
이 문제는 동적 프로그래밍(Dynamic Programming)과 재귀 호출을 활용하여 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
- 기저 조건(Base case): n이 1이면 True를 반환합니다.
- n이 이미 방문(visited)된 적이 있다면 False를 반환합니다. 이는 무한 루프에 빠졌음을 의미합니다.
- 현재 n을 방문 처리합니다.
- n을 문자열로 변환한 뒤 각 자릿수를 리스트로 만듭니다.
- 모든 자릿수의 제곱합을 계산하여 temp에 저장합니다.
- temp와 방문 목록을 인자로 하여 함수를 재귀적으로 호출합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
return self.solve(n,{})
def solve(self,n,visited):
if n == 1:
return True
if n in visited:
return False
visited[n]= 1
n = str(n)
l = list(n)
l = list(map(int,l))
temp = 0
for i in l:
temp += (i**2)
return self.solve(temp,visited)
ob1 = Solution()
op = ob1.isHappy(19)
print("Is Happy:",op)입력
19
출력
Is Happy: True
코드 설명
isHappy 메서드는 초기 호출을 담당하며, 실제 로직은 solve 메서드에서 처리됩니다. solve 메서드는 먼저 n이 1인지 확인하여 기저 조건을 검사하고, 이미 방문한 숫자라면 False를 반환하여 무한 재귀를 방지합니다. 그 후 숫자를 문자열로 변환해 각 자릿수를 추출하고, 자릿수들의 제곱합을 구한 뒤 그 결과값으로 재귀 호출을 반복합니다. 방문 여부를 딕셔너리(집합 역할)로 관리함으로써 사이클 감지가 가능해집니다.