leetcode easy : Happy Number

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

Happy Number - LeetCode

 

해시테이블은 왠지 쓰면 안될거같았다.

간단한 숫자문제라서 O(1) 스페이스로 푸는게 관건일거같았음.

문득 떠오른건 예전에 Linked List에서 slow pointer & fast pointer 기법을 썼던 것.

두 숫자를 두고 하나는 두번씩 컨버팅하고 하나는 한번씩만 컨버팅해서 둘중 하나라도 1이 되면 n은 happy number고 1이 아닌데 둘이 같아지면 사이클이 있는것이다.

 

class Solution:
    def isHappy(self, n: int) -> bool:
        def convert(num):
            result = 0
            while num > 0:
                result += (num % 10) ** 2
                num //= 10
            return result
        
        p1 = n
        p2 = n

        p1 = convert(p1)
        p2 = convert(convert(p2))

        while p1 != p2 and p1 != 1 and p2 != 1:
            p1 = convert(p1)
            p2 = convert(convert(p2))
        
        return p1 == 1 or p2 == 1