[Leetcode,c++] Add Digits

문제

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

Add Digits - LeetCode

 

코드

(1) 재귀, 반복문을 사용한 풀이

class Solution {
public:
    int addDigits(int num) {
        int temp1=0, temp2=0, ans=num;
        while(true){
            while(num>9){
                temp1 = num%10;
                temp2 = num/10;
                ans = temp1 + temp2;
                num = ans;
            }
            if(num<10){
                num = ans;
                return num;
            }
        }
        
    }
};

 

(2) 조건식을 활용하여 O(1) 시간 복잡도로 해결한 풀이

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

 

풀이

이 문제는 2^31- 1까지 들어오는 자연수의 각 자릿수를 한 자릿수가 될 때까지 더해서 출력하는 문제입니다. 

처음에는 반복문을 활용해서 각 자릿수를 떼어가며 풀었지만 문제에서 Follow up: Could you do it without any loop/recursion in O(1) runtime? 라는 조건을 준 것을 보면 반복문이나 재귀를 사용하지 않고 O(1)의 시간으로 해결하라는 문제이기에 좀 더 고민이 필요했던 문제였습니다. 

결과적으로 O(1)로 해결한 두 번째 풀이를 보면 알겠지만 9로 모듈러 연산을 했을 때의 값이 결과적으로 우리가 원하는 값이 됨을 알 수 있는데 그 이유는 숫자 9라는 값을 자세히 살펴보면 아래의 특징을 지니고 있습니다.

출처: 위키피디아

4번째 특징을 잘 살펴보면 9에 어떤 수를 곱하더라도, 나오는 값의 각 자리 숫자를 모두 합하면 9의 배수 값이 됩니다. 

else if(num%9==0) return 9;

따라서 위 코드 조건 부분은 9로 mod연산을 계속해주었을 때 0이 나온다면 9의 배수가 되기에 결론적으로 9가 됩니다.

 

더 자세히 알아봅시다. 아래의 표는 1~100까지의 digits 수 결과입니다.

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
---------
10 1
11 2
12 3
13 4
14 5
15 6
16 7
17 8
18 9
--------
19 1
20 2
21 3
22 4
23 5
24 6
25 7
26 8
27 9
-------
28 1
29 2
30 3
31 4
32 5
33 6
34 7
35 8
36 9
-------
37 1
38 2
39 3
40 4
41 5
42 6
43 7
44 8
45 9
------
46 1
47 2
48 3
49 4
50 5
51 6
52 7
53 8
54 9
--------
55 1
56 2
57 3
58 4
59 5
60 6
61 7
62 8
63 9
--------
64 1
65 2
66 3
67 4
68 5
69 6
70 7
71 8
72 9
--------
73 1
74 2
75 3
76 4
77 5
78 6
79 7
80 8
81 9
--------
82 1
83 2
84 3
85 4
86 5
87 6
88 7
89 8
90 9
-------
91 1
92 2
93 3
94 4
95 5
96 6
97 7
98 8
99 9
------
100 1

9개의 수가 주기적으로 값이 1~9가 나옴을 알 수 있습니다. mod 9 연산을 행하는 것입니다.