258. Add Digits

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

Add Digits - LeetCode

 

38 -> 3 + 8 -> 11 -> 1 + 1 -> 2

주어진 숫자를 모두 더해서 한자리 숫자로 만드는 문제

 

n이 10 이하가 될 때까지 재귀 함수를 통해서 합산한 풀이는 아래와 같다.

class Solution {
public:
    int rec(int n) {

        if (n < 10) {
            return n;
        }

        int result = 0;
        while (n) {
            int cand = n % 10;
            result += cand;
            n = n / 10;
        }

        return rec(result);
    }

    int addDigits(int num) {
        return rec(num);
    }
};

 

비슷한 방법으로 string 변환하여서 푼 코드는 아래와 같다.

class Solution {
public:
    int rec(string s) {

        const int size = s.size();
        if (size == 1) {
            return atoi(s.c_str());
        }

        int cand = 0;
        for (int i = 0; i < size; i++) {
            cand += s[i] - '0';
        }

        string ss = to_string(cand);
        return rec(ss);
    }

    int addDigits(int num) {
        int sol = 0;
        string s = to_string(num);
        return rec(s);
    }
};

 

위 두개의 코드는 단순 구현이다. 부족한 점이 보인다. 중복되는 계산을 줄이는 방법을 생각해보자.

 

나머지 연산을 이용하는 방법

0 1 2 3 4 5 6 7 8 9 -> 0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 -> 1 2 3 4 5 6 7 8 9 10(this is just 1)
20 21 22 23 24 25 26 27 28 29 -> 2 3 4 5 6 7 8 9 10(1) 11(2)

9로 나누는 나머지는 항상 1자리 수를 표현한다. 이런 풀이까지 접근하려면 얼마나 오래 걸릴 것인가..

Look carefully to how a number maps to the single digits. For example 11 is the same as 29 which maps to 2. Then looking at 11 and 29 think of a relationship of how both of them maps to 2. You then realize that 11 % 9 = 29 % 9.

class Solution {
public:
    int addDigits(int num) {
        if(num % 9 == 0 && num >= 9)
            return 9; 
        return num % 9; 
    }
};