[LeetCode] #202. Happy Number

문제 :

정수가 주어지고, 그 정수의 각 자릿수를 1이 될때까지 제곱하여 더해준다. 만약, 결괏값이 1으로 수렴한다면 True를 반환하고, 그렇지 않다면(무한루프), False를 반환한다.

 

이 문제를 처음 보고 써야할 자료구조를 생각해내지 못했다. 그냥 brute force로 계속 곱해 1이 된다면 True, 아니면 False를 반환하려고 했는데, 무한 루프를 돌 경우를 알려주는 플래그는 존재하지 않는다.. 그래서 도대체 어떻게 해결하지 한참을 고민했다. 결국 오늘 문제는 내 스스로 해결하지 못하고 Solution의 도움을 받았다. 아래 Solution을 보고 코드를 분석 해보도록 하겠다.

 

아래는 내가 제출한 코드가 아닌 Solution에서 가져온 코드이다.

class Solution:
    def isHappy(self, n: int) -> bool:
        hset = set()
        while n != 1:
            if n in hset:
                return False
            hset.add(n)
            n = sum([int(i) ** 2 for i in str(n)])
        else:
            return True

 

- 집합 선언:
hset = set()

hset은 정수를 저장하는 집합이다. 집합은 중복을 허용하지 않으므로, 이전에 계산된 값이 다시 나타날 경우 무한 루프에 빠진 것을 감지할 수 있다.

- 반복문:

while n != 1:
n이 1이 아닐 때까지 반복한다. 1이 되면 True를 반환하고 종료한다.

- 무한 루프 감지:

if n in hset:
    return False
현재 n이 hset에 이미 존재하면, 이는 무한 루프에 빠졌다는 의미이므로 False를 반환한다.

- 집합에 현재 숫자 추가:

hset.add(n)
현재 n을 집합에 추가한다.

-새로운 숫자 계산:

n = sum([int(i) ** 2 for i in str(n)])
현재 숫자의 각 자릿수를 제곱하여 더한 값을 새로운 n으로 설정한다. 이를 위해 숫자를 문자열로 변환하고, 각 자릿수를 제곱하여 합한다.

- 결과 반환:
else:
    return True
n이 1이 되면 True를 반환합니다.

 

사실 이 문제는 자료구조 / 알고리즘적 사고 보다는 수학적 사고에 가까운 문제였다고 생각한다. 중복을 허용하지 않는 집합을 사용해 무한루프에 빠지는지 아닌지를 판별하는게 가장 큰 이 문제의 trick이였는데, 나는 생각해내지 못했다 :(