[Top Interview Questions] 202. Happy Number

정답)

class Solution:
    def isHappy(self, n: int) -> bool:
        res = 0
        seen = set()

        while res != 1:
            res = 0
            
            while n:
                res += (n % 10)**2
                n //= 10

            if res in seen:
                return False
            seen.add(res)

            n = res
        
        return True

문제)

문제출처

 

숫자 n이 행복한지 결정하는 알고리즘을 작성하시오.

 

행복한 숫자는 다음과 같을 때 결정됩니다:

- 아무 양수가 주어졌을 때 양수의 각 자릿수를 제곱한 값들을 더하시오

- 위 단계를 합이 1이 될 때까지 반복하시오. 1이 나오지 않는 경우에는 같은 숫자들이 반복해서 나옵니다.

- 각 자릿수의 합이 1로 끝나는 숫자가 행복한 숫자입니다.

 

행복한 숫자가 주어지면 True, 아니라면 False를 리턴하시오.

 

예시 1)

n = 19

output = True

1 + 81 = 82

64 + 4 = 68

36 + 64 = 100

1 + 0 + 0 = 1

 

예시 2)

n = 2

output = False

4

16

1 + 36 = 37

9 + 49 = 58

...

36 + 1 = 37

(계속 반복)

풀이)

각 자릿수를 더해줍니다.

1을 발견할 때까지 계속해서 각 자릿수를 더하고 그 더해진 값을 세트에 저장해 줍니다.

 

만약 더한 값이 1이라면 루프를 끝내 True를 리턴하고

더한 값이 이미 세트에서 저장된 값이라면 False를 리턴합니다.

 

def isHappy(self, n: int) -> bool:
        덧셈을 저장할 변수 res
        이때까지 찾은 덧셈을 저장할 세트 변수 seen
        
        res가 1이 아닐동안:
            res는 0
            res에 n의 각 자릿수들을 제곱해 더해줌

            res가 seen에 있다면
                False를 리턴
                
            seen에 res를 저장

            n = res
        
        True를 리턴

초기세팅)

n이 주어졌을 때 n의 각 자릿수를 제곱하여 더한 값을 저장해 줄 res 변수가 필요합니다.

 

그리고 문제에서 만약 숫자가 행복하지 않다면 같은 숫자가 반복되는 루프가 발생한다고 했기 때문에 같은 숫자가 나왔는지 확인할 세트 seen 또한 만들어줍니다.

 

매번 덧셈을 할 때마다 res가 seen에 존재하는지 확인하고 존재하지 않는다면 seen에 새롭게 추가해줄 겁니다.

 

※ 여기서 seen을 리스트가 아닌 세트를 사용하는 이유는 세트를 이용하는 것이 더 빠르기 때문입니다. 세트가 임의의 순서로 원소를 저장하는 불편함이 있지만 원소가 세트에 존재하는지 확인하는 것은 리스트에서 확인하는 것보다 빠릅니다. 고로 지금 같이 원소가 존재하는지 확인만 해도 되는 상황일 때는 세트를 사용하겠습니다.

 

def isHappy(self, n: int) -> bool:
        res = 0
        seen = set()

루프)

이제 덧셈의 과정을 1이 반복될 때까지 해보겠습니다.

 

루프 하는 과정에서 계속해서 res에 새로운 덧셈 값을 저장해 줘야 되기 때문에 매 루프 시작할 때마다 res는 0으로 지정해 주겠습니다.

 

그리고 n이 0이 될 때까지

res에 n의 끝자리를 제곱하여 더해주고

n의 끝자리를 다음 자릿수로 대체해 줍니다.

 

while n의 과정

def isHappy(self, n: int) -> bool:
        res = 0
        seen = set()

        while res != 1:
            res = 0
            
            while n:
                res += (n % 10)**2
                n //= 10

res가 이미 존재했던 값인지)

아까 말했듯이 숫자가 행복한지 확인하려면 이미 존재했던 숫자인지 확인해야 됩니다.

 

아까 만들어둔 세트 seen에 존재하는지 확인하고 만약 존재하면 False를 리턴하고

존재하지 않는다면 seen에 새롭게 추가합니다.

 

그리고 다음 루프에서 새로운 숫자의 자릿수를 더해주기 위해서 n 또한 res의 값을 저장해 n을 업데이트시켜줍니다.

 

n을 업데이트하는 이유

그렇게 res가 1이라면 while 루프가 끝나고 True를 리턴하면 되겠습니다.

 

def isHappy(self, n: int) -> bool:
        res = 0
        seen = set()

        while res != 1:
            res = 0
            
            while n:
                res += (n % 10)**2
                n //= 10

            if res in seen:
                return False
            seen.add(res)

            n = res
        
        return True

디버깅)

n = 19

res = 0

seen = []

 

(while res != 1)

res = 0

 

(while 19)

res = 81

n = 1

 

(while 1)

res = 82

n = 0

 

seen = [82]

n = 82

 

(while res != 1)

res = 0

 

(while 82)

res = 4

n = 8

 

(while 8)

res = 68

n = 0

 

seen = [82, 68]

n = 68 

 

...

 

(while res != 1)

res = 0

 

(while 100)

res = 0

n = 10

 

(while 10)

res = 0

n = 1

 

(while 1)

res = 1

n = 0

 

seen = [82, 68, ..., 1]

n = 1

 

return True

 

 

이번 문제는 따로 공간 복잡도의 제약도 없고 문제만 잘 읽었다면 나름 잘 풀렸을 거 같네요. 문제들이 갈수록 어려워지면 좋겠는데 어떨 땐 어렵다가 어떨 땐 쉽게 나오니 혼란스럽네요. Top Interview Questions를 전부 다 풀면 백준 문제들을 풀어볼까 합니다. 한국어로 설명하는데 굳이 릿코드를 해야 싶기도 하고 우리나라에선 나름 권위 있는 사이트니 고려해 봐야겠네요.

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)