LeetCode-202 Happy Number 파이썬 풀이

Happy Number - LeetCode

문제

주어진 숫자 n이 Happy Number인지 판별하는 문제입니다.

HappyNumber는 n의 각 자리수를 제곱하여 더한 값을 다시 n으로 보고 각 자리수를 제곱하여 더하고를 반복하여 결과가 1로 끝날 경우 HappyNumber입니다. 예시에서 주어진 19의 경우 1과 9를 제곱하여 (1,81) 더한 값 82를 다시 n으로 봅니다. 또 각 8과 2를 제곱하여 (64,4)를 더한 값 68을 n으로 보고 6과 8을 제곱하면 (36,64)가 되어 100이 됩니다. 100은 (1,0,0)으로 결과값이 1이 되어 HappyNumber 입니다. 2의 경우 2 -> 4 -> 8 -> 64 -> (36 + 16) 52 -> (25 + 4) 29 -> (4+81) 11->2 로 반복되어 HappyNumber가 아닙니다.

풀이

 

HappyNumber가 맞는 숫자는 판별하기 쉽습니다.

1. 각자리수 만큼 제곱하고, 그 값을 result에 저장해 둡니다.

2. result가 1이 아닐경우 result를 n으로 설정하여 반복합니다. 

 

이 방법의 경우 HappyNumber가 맞을 때 복잡한 연산이 없기 때문에 빠르게 결과가 도출되지만 아닐 경우에 무한루프로 돌게되어 Time Limit Exceeded를 마주하게 됩니다. 그렇다면 HappyNumber가 아닌 경우를 고민해 보아야 합니다. 앞서 살펴보았던 2는 다시 2가 반복되었습니다. 따라서 다른 숫자도 반복되는 경우가 있는 지 살펴보고 반복된다면 HappyNumber가 아닌 경우를 중복으로 판별하면 됩니다.

예시 1: 4> 4 -> 16 -> (1+36) 37 -> (9+49) 58 -> (25+64) 89 -> (64+81) 145-> (1+16+25) -> 42 -> (16+4) 20 -> 4

예시 2: 11> 2-> 4-> 16 -> .... 20 -> 4

 

예시 처럼 HappyNumber가 아닌 경우 result가 반복되는 때가 있습니다. 따라서 매 result를 history 라는 배열에 저장해두었다가 result가 history에 존재하는지 여부를 판단하여 HappyNumber가 아닌경우 무한 루프를 빠져나오면 됩니다.

class Solution:
    def isHappy(self, n: int) -> bool:
        if n == 1: return True
        history = []
        while(n!=1):
            result = 0
            for i in range(0,len(str(n))):
                result += int(str(n)[i]) * int(str(n)[i])
            if result==1:
                return True
            else:
                n = result
                if result in history:
                    return False
                history.append(result)