23.04.26. 풀었던 문제들

Leetcode 258. Add Digits

어떤 수 n이 있을 때 n의 자리수를 모두 합쳐 n을 만든다. n이 한 자리가 될때까지 이것을 반복하는 문제.

 

첫 번째 접근

 trivial하게 단순 구현으로 접근. 

// Runtime 0 ms Beats 100%
// Memory 5.9 MB Beats 63.10%

class Solution {
public:
    int addDigits(int num) {
        while(num >= 10){
            int temp = 0;
            while(num){
                temp += num % 10;
                num /= 10;
            }
            num = temp;
        }
        return num;
    }
};

 

시간복잡도

 n이 INT_MAX면 $2^32$, 약 21억이다. 그러나 21억의 모든 자리수를 합쳐도 약 180정도로 3자리로 줄게 된다. 따라서 O(logn)이라 볼 수 있다.

 

공간복잡도

 추가 공간을 사용하지 않음. 상수만 사용한다. O(1).

 

 

두 번째 접근

 follow-up으로 반복문이나 재귀 없이 O(1)로 풀 수 있는 방법을 제시한다. 

 일단 최종적인 정답 x는 0 <= x <= 9이다. 그야 한 자리수니까 당연하다.

 그렇다면 생각을 해 봤을 때, 1부터 쭉 숫자를 나열해 보고 이것들의 정답을 유추해 보자

• 1 - 1
• 2 - 2
• ...
• 9 - 9
• 10 - 1
• 11 - 2
• ...
• 18 - 9
• 19 - 10 - 1
• 20 - 2
• ...
• 27 - 9
• 28 - 10 - 1
• ...

 이렇게, 9의 배수마다 수가 반복되는 것을 알 수 있다. 3자리 수로 넘어가도 동일하다.

// Runtime 7 ms Beats 16.24%
// Memory 6 MB Beats 63.10%

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

 

시간복잡도 & 공간복잡도

 자명하게 O(1)

 

 

후기

 이걸 digital root라고 한다. wikipedia 링크를 걸겠다.