어떤 양의 정수 n이 주어졌을 때, 이 숫자가 행복한 수(Happy Number)인지 판별하는 문제를 살펴보겠습니다.
행복한 수(Happy Number)란?
행복한 수는 임의의 양의 정수에서 시작하여, 그 수를 각 자릿수의 제곱의 합으로 반복해서 대체했을 때 최종적으로 1에 도달하는 수를 의미합니다. 만약 1에 도달하지 못하고 같은 값들이 무한히 반복되는 사이클에 빠진다면 그 수는 행복한 수가 아니며, 과정을 거쳐 1에 도달하는 모든 수가 행복한 수입니다.
예시: 19는 행복한 수일까?
입력이 19일 때 결과는 true입니다. 과정을 단계별로 살펴보면 다음과 같습니다.
- 12 + 92 = 82
- 82 + 22 = 68
- 62 + 82 = 100
- 12 + 02 + 02 = 1
마지막에 1에 도달했으므로 19는 행복한 수입니다.
문제 해결 접근 방식
- 재귀 + 방문 기록(메모이제이션): 동적 프로그래밍 기법을 활용해 이미 계산한 숫자를 추적합니다.
- 기저 사례(Base Case): n이 1이면 true를 반환합니다.
- 사이클 감지: n이 이미 방문한 숫자라면 false를 반환합니다. 이는 무한 루프에 빠졌다는 의미입니다.
- 현재 숫자 n을 방문 처리합니다.
- n을 문자열로 변환한 뒤 각 자릿수를 리스트로 분리합니다.
- 모든 자릿수의 제곱합(temp)을 계산합니다.
- temp 값을 인자로 하여 함수를 재귀적으로 호출합니다.
파이썬 구현 코드
class Solution(object):
def isHappy(self, n):
return self.solve(n, {})
def solve(self, n, visited):
# 기저 사례: 1에 도달하면 행복한 수
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)
ob = Solution()
print(ob.isHappy(19))입력
19
출력
True
동작 원리 정리
위 코드는 isHappy 메서드가 빈 딕셔너리(방문 기록)와 함께 solve를 호출하는 것으로 시작됩니다. solve는 먼저 n이 1인지 확인하고, 1이라면 true를 반환합니다. n이 이미 방문 기록에 있다면 사이클에 빠진 것이므로 false를 반환합니다. 그렇지 않으면 n을 방문 처리한 후, 각 자릿수의 제곱합을 계산하여 그 결과값으로 자기 자신을 다시 호출합니다. 이 과정은 1에 도달하거나(행복한 수), 사이클이 감지될 때까지(행복한 수가 아님) 반복됩니다.
시간 복잡도 측면에서 보면, 자릿수 제곱합 연산 한 번은 자릿수에 비례하여 O(log n)이며, 어떤 큰 수든 몇 번의 변환만 거치면 작은 범위(세 자리 수 기준 최대 243)로 수렴하므로 전체 실행 시간은 매우 짧습니다.
마무리
행복한 수는 코딩 테스트에서 해시 셋을 이용한 사이클 감지를 연습하기 좋은 대표적인 문제입니다. 참고로 100 이하의 행복한 수는 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100이 있습니다. 위 코드의 입력값을 바꿔가며 직접 실행해 보면 행복한 수의 특성을 더 깊이 이해할 수 있습니다.