[LeetCode] 258 | Add Digits | Python

---

문제 링크: https://leetcode.com/problems/add-digits/

---

문제

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

---

조건

• 0 <= num <= $2^{31}$ - 1

---

내 풀이

처음에는 단순하게 recursion을 사용해서 1)처럼 풀었다.

num의 각 자리수를 더한 후, 그 합이 한자리 수가 아니면 이를 반복하는 형식이다.

 

그런데 follow up에 'Could you do it without any loop/recursion in O(1) runtime?'라고 써있어서 도전해봤다.

이 방법은 위의 방법에서 조금 발전한 것이다.

num의 각 자리수를 더할 때, 그 순간의 합이 한자리 수가 아니면 더하는 방식이다.

ex) 472 $\rightarrow$ (4+7) + 2 $\rightarrow$ (11) + 2 $\rightarrow$ (1+1) + 2 $\rightarrow$ (2) + 2 $\rightarrow$ 4

---

코드

1) recursion 사용해서 단순하게

class Solution:
    def addDigits(self, num: int) -> int:
        while len(str(num)) > 1:
            t_num = 0
            for n in str(num):
                t_num += int(n)
            num = t_num
            
        return num

 

2) recursion 사용하지 않고 O(1)만에

class Solution:
    def addDigits(self, num: int) -> int:
        if num > 9:
            t_num = 0
            for n in str(num):
                t_num += int(n)
                if t_num > 9:
                    t_num = t_num%10 + t_num//10
                    
            num = t_num
            
        return num