Leetcode 문제 258번 Add Digits

문제 출처:https://leetcode.com/problems/add-digits/

Add Digits - LeetCode

Leetcode 258번 문제 Add Digits

---

해당 문제는 각 자리수의 숫자들을 다 더한 값을 한자리가 될 때까지 계속하는 것입니다. 저는 추상적으로 접근하여 다음과 같은 실행되는 코드를 얻을 수 있었습니다.  

class Solution {
public:
    int addDigits(int num) {
        int answer = num, sum = 0 ;
        while(10 <= answer){
            while(answer != 0){
                sum += answer%10 ;
                answer /= 10 ;
            }
            answer = sum ; 
            sum = 0 ;
        }
        return answer ;
    }
};

처음에는 잘 실행되는 것을 확인하고 그냥 넘겼었습니다. 하지만 저를 자극하는 한마디때문에 다시 할수 밖에 없었습니다.

도발이냐..? 

제가 구현한 코드는 Time Complexity가 ${O(n^2)}$으로 그리 빠른 코드는 아닙니다. ${O(1)}로 구현하라는 것은 재귀적인 부분을 포함하라는 것이고 조금 더 고민해서 다음 코드를 만들 수 있었습니다. 

class Solution {
public:
    int addDigits(int num) {
        if(num < 10)
            return num ;
        else
            return addDigits(sumDigits(num)) ;
    }
    
    int sumDigits(int num) {
        if(num == 0)
            return 0 ;
        else
            return num % 10 + sumDigits(num/10) ;
    }
};

확실히 처음 구했던 답에 비해서 5ms 빠른 속도를 보여줬습니다. 

---

해당 문제는 Github에서도 보실 수 있습니다:

https://github.com/gurcks8989/CodingTest/blob/master/LeetCode/P258_Add_Digits.cpp

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든 환영입니다.