개요

[HackerRank]RecursiveDigitSum

We define super digit of an integer using the following rules:

Given an integer, we need to find the super digit of the integer.

If has only digit, then its super digit is .
Otherwise, the super digit of is equal to the super digit of the sum of the digits of .

접근방식

문제를 간단히 요약하면 숫자가 string형으로 함수인자로 들어오면 자릿수의 합을 더한다.
또, 그 합에 해당하는 숫자의 각 자릿수의 합을 더하는 식으로 반복해서
마지막 한 자리 숫자를 반환해야한다.

superDigit함수에 각 자릿수를 더하는 부분을 구현한 후,
해당 함수를 다시 superDigit함수의 인자로 넣고 함수를 재귀호출하는 방식으로 구현했다.

문제는 처음 들어오는 값인 n의 크기가 엄청크다.
또한 k개만큼 n을 이어붙여야하므로 숫자가 어마어마하게 크다.

따라서 그냥 n을 k개 붙이고 연산을 시작하기보단
n의 자릿수의 합을 미리 구하고 k를 곱하는 식으로 구현했다.

전체 코드

int superDigit(string n, int k) {
    if(n.size()==1) return n[0]-'0';
    long long sum=0;

    string next="";
    for(char elem: n){
        sum += elem -'0';
    }
    long long tmp=sum;
    tmp*=k;
    while(tmp>0){
        next += tmp%10 +'0';
        tmp/=10;
    }
    reverse(next.begin(),next.end());
    return superDigit(next, 1);
}

생각

처음에 k개 붙이는 방식이 아니라 k번 자릿수를 더해라라는 문제로 보고 접근했다.
아무래도 문제가 영어이다보니 신중하게 꼼꼼히 읽는 연습이 더 필요한 것 같다.