[리트코드 LeetCode] Happy Numebr (Python)

Happy Number

• https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/815
• 분류: Top Interview Questions - Medium - Math

문제

• 주어진 숫자 n이 happy한지 판단하는 알고리즘을 작성하라.
• happy number는 다음의 과정을 통해 결정된다
  • 아무 양의 정수로 시작하여 숫자를 각 자릿수의 제곱의 합으로 바꿈
  • 숫자가 1이 될 때까지 위의 과정을 반복하라 (1이 된다면 연산을 반복해도 계속 1에 머물 것이고, 1이 되지 않는다면 영원히 1이 없는 사이클이 반복될 것임)
  • 1이 되어 끝나는 숫자는 happy하다.
• type n: int / rtype: bool

예시

Example 1:
Input: n = 19
Output: true
Explanation:
	1^2 + 9^2 = 82
	8^2 + 2^2 = 68
	6^2 + 8^2 = 100
	1^2 + 0^2 + 0^2 = 1

Example 2:
Input: n = 2
Output: false
2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> ... 

조건

• 1 <= n <= 2^31 - 1

풀이

set 활용

n을 string으로 변환한 후 각 자릿수에 대해 제곱 연산을 수행해 다음 숫자를 구하고 그 숫자가 1이면 true 리턴, 아니면 set에 그 수 저장

다음에 그 수가 또 나온다면 (연산의 결과가 set에 있는 수라면) 사이클이 반복되고 있는 것이므로 false 리턴

class Solution(object):
    def isHappy(self, n):
        prev = set()
        while True:
            num = str(n)
            total = 0
            for i in num:
                total += int(i) ** 2
            if total in prev:
                return False
            elif total == 1:
                return True
            prev.add(total)
            n = total

Time: O(klog(n)) / Space: O(k)

Runtime: 15 ms (beats 93.16%) / Memory Usage: 13.2 MB (beats 90.08%)

 

시간복잡도, 공간복잡도에 대한 설명

• https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/815/discuss/56915/My-Python-Solution

The time complexity of this implementation is O(klog(n))n is the input numberk is the number of iterations required to determine whether the number is happy.Each iteration of the while loop involves calculating the sum of the squares of the digits in n, which takes log(n) time (since there are log(n) digits in the number n, and each digit requires a constant amount of time to square and sum). Therefore, the time complexity of each iteration of the while loop is O(log(n))Overall, the while loop runs at most k times, so the total time complexity of the algorithm is O(klog(n))In practice, however, the value of k is typically quite small for most input numbers, so the actual time and space complexity of this implementation is usually much lower than the worst-case complexity.

The space complexity of this implementation is also O(k), since the set of visited numbers can contain at most k numbers. Note that the maximum value of k is unbounded, so the space complexity could potentially be very large for very large input numbers.

 

sum, list를 이용해 단축한 코드

def isHappy(self, n):
        seen = set()
        while n not in seen:
            seen.add(n)
            n = sum([int(x) **2 for x in str(n)])
        return n == 1

Runtime: 24 ms (beats 46.89%) / Memory Usage: 13.5 MB

깔끔하긴 하지만 리스트를 이용한 sum을 쓰지 않는 편이 속도와 메모리 면에서 더 나은 성능을 보여준다.

 

str-int 형변환을 거치지 않고 % 10을 이용하여 자릿수별 연산을 하는 경우

형변환을 거치지 않기 때문에 더 빠르다. 

class Solution(object):
    def isHappy(self, n):
        seen = set()
        while n != 1:
            _sum = 0
            while n:
                _sum += (n % 10) ** 2
                n //= 10
            if _sum in seen:
                return False
            seen.add(_sum)
            n = _sum
        return True

Runtime: 12 ms (beats 97.5%) / Memory Usage: 13.2 MB (beats 99.43%)