LeetCode 258(Add Digits, Python)

1. 문제 링크 

• https://leetcode.com/problems/add-digits/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

2. 문제 설명

• 정수 num이 주어졌을 때, 반복해서 각 자릿수를 더하여, 더한 값이 한자리가 될 때까지 반복하여, 해당 값을 반환 
• 예시) num=38이라면,
  • 3과 8을 더하면 11. 11은 두자리수이므로, 계속 진행 
  • 1과 1을 더하면 2. 2는 한자리 수이므로, 2를 반환.

3. 처음 풀이 

• num의 len가 1이 아닐때까지 while문을 반복하며,
  
  • str(num)의 각 자릿수를 더한 값을 num으로 업데이트해준다.
• 그리고 num의 len이 1이 되는 순간 while문이 종료되고, 이 때 num을 반환한다. 

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

 

4. 다른 풀이

• 문제의 Follow up란에, loop나 recursion을 사용하지 않고 O(1) runtime으로 해당 문제를 해결할 수 있는지 적혀있었다. 
• 아래가 출제자의 의도인 풀이인지는 모르겠으나, 다음과 같은 풀이도 있었다. 
  • 만약 num이 0이면 0을 반환하고, 
  • 9로 나눈 나머지가 0이면 9를 반환하고, 
  • 그 이외의 케이스에는 9로 나눈 나머지를 반환! → 숫자 감각이 남달라야 할 것 같은데 이게 어떻게 되는거지? 
• 위의 예시로 보면, 38은 9로 나눈 나머지가 2로, 아래의 로직으로 풀어진다.

class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0 :
            return 0;
        elif num % 9 == 0:
            return 9;
        else:
            return num % 9;

• 계속해서 9로 나눌 때 0,1,2,...,8까지 순환을 한다. 따라서 어떤 수의 각 자릿수를 더한 결과를 다시 더할 때, 
• 최종 결과가 9의 배수가 되면, 그 수 자체가 9로 나누어떨어지게 된다. 
• https://en.wikipedia.org/wiki/Digital_root

Digital root - Wikipedia