[LeetCode] 258. Add Digits

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

Add Digits - LeetCode

Add Digits - Easy

 

웬만하면 Easy 문제들은 작성하지 않으려 했는데, 풀다보니 신기하고 재밌어서 포스팅한다.

integer 형식의 수가 주어졌을때, 그 수의 자리수들을 각각더하고 다시 그 결과의 자리수들을 각각더하고.. 를 한자리수가 될때까지 반복해 나오는 결과값을 구하는 문제다.

 

마냥 반복문을 돌려서 값을 얻을 수 있고 생각하기도 쉬운 문제다.

처음엔 그러려 했으나, 

 

Follow up: Could you do it without any loop/recursion in O(1) runtime?

 

라는 글귀를 보고 생각을 한번 더 해보고, 쭉 적어 봤다.

0 1 2 3 4 5 6 7 8 9 10 11 12 18 19 20 21 22 27 28 29 30

0 1 2 3 4 5 6 7 8 9 1   2   3  9   1  2  3   4   9  1   2   3

 

처음 0을 제외하고는 계속 1,2,3,4,5,6,7,8,9가 반복된다.

생각해보면 당연하다. 자리수를 더한다고 해도 결국 원래수도 이전수에서 1더해지고, 자리수도 일의자리가 이전수보다 1증가하게 될테니.. (9일 경우엔 어차피 1로 돌아가니)

 

따라서 원래수에서 1을 빼준 후, 9로 나눈 나머지를 구한뒤 다시 1을 더해주면 된다.

 

전체 풀이 코드

class Solution {
public:
    int addDigits(int num) {
        if (!num) return 0;
        return (num-1)%9+1;
    }
};