LeetCode 202(Happy Number, Python)

1. 문제 링크

• https://leetcode.com/problems/happy-number/

Happy Number - LeetCode

 

2. 문제 설명

• 주어진 수가 happy 넘버인지 따져서 True, False 반환
  • 여기서 happy 넘버란 주어진 규칙을 반복했을 때 1이 나올 수 있는지 따지는 것
    • 규칙: 각 자릿수 제곱을 합하여 그 다음의 수를 만드는 것
  • 예시1) 19 → 1^2 + 9^2 = 82 → 8^2 + 2^2 = 68 → 36 + 64 = 100 → 1 + 0 + 0 = 1 이므로 True 반환
  • 예시2) 2 → 4 → 16 → 1 + 36 = 37 → 9+ 49 → 58 → 25 + 64 = 89 → 64 + 81 = 145 → 1 + 16 + 25 = 42 → 16 + 4 = 20 → 4+ 0 = 4 로 계속 반복이 되며 1이 나오지 않으므로 False 

3. 처음 풀이

• 처음 이 문제를 봤을 땐, 당연히 while loop를 돌리면 time limit 혹은 무한 루프에 빠질 거라고 생각했음. 
• 하지만, 문제의 난이도가 easy 생각해봤을 때 while을 돌렸을 때 답이 유한해서 무한 루프에 빠지지 않음 
  • 수가 아무리 커도 happy number 가 아니라면 loop가 생길 수 밖에 없음
  • 9999라고 해도 81을 네 번 더해서 324로 처음 수인 9999보다 작으며
    • 결국 1~9999까지 유한한 수가 후보이므로 결국 1 or 이미 존재하는 수가 등장할 수 밖에 없음
  • 따라서 나온 수를 저장하면서 1이 나오면 True, 이미 나온 수가 나오면 False를 반환하도록 코드 작성

class Solution:
    def isHappy(self, n: int) -> bool:
        
        n_hist = []

        while True:
            
            sum=0
            for i in str(n):
                sum += int(i)**2 
            
            if sum in n_hist:
                return False

            n_hist.append(sum)

            if sum == 1:
                return True

            n = sum

 

4. 다른 풀이

• two pointers, 토끼와 거북이 전략
  • 두 칸씩 가는 포인터와 한 칸씩 가는 포인터를 만들어 이 둘이 같아지는 순간이 있는 지 따지면 루프가 있는지 확인 가능
  • 기존에 탐색한 내용을 저장하는 리스트나 집합이 없어서 메모리를 추가적으로 사용하지 않을 수 있음

class Solution:
    def isHappy(self, n: int) -> bool:
        slow = n
        fast = self.squared(n)

        while slow != fast and fast != 1:
            slow = self.squared(slow)
            fast = self.squared(self.squared(fast))

        return fast == 1

    def squared(self, n):
        result = 0
        while n > 0:
            last = n % 10
            result += last * last
            n = n // 10
        return result

5. 배운점 

• 연결 리스트의 사이클 존재 유무를 따질 때, "속도가 달라도 사이클이 있으면 언젠가 만난다"의 토끼와 거북이 전략을 떠올렸었는데,
• 이번에도 같은 '루프'이니 그 전략을 사용할 수 있음