[LeetCode] - 258. Add Digits

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Add Digits" 문제입니다.

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

 

문제 : 

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

---

Example 1 :

Input : num = 38

Output : 2

Explanation : The process is 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 Since 2 has only one digit, return it.

 

Example 2 :

Input : num = 0

Output : 0

 

Constraints :

0 <= num <= 2^31 - 1

 

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

---

이 문제는 주어진 정수 num의 모든 자릿수를 반복적으로 더하여 결과가 한 자리 숫자가 될 때까지 계산한 후 그 결과를 반환하는 것입니다. 하지만 컨디션이 조금 어려운 게, 반복문, 재귀 없이 풀어보라는 겁니다. 저는 이게 무조건 수학적인 접근이라고만 짐작이 갔지만, 결국 풀지는 못했습니다. 하지만 반복문을 쓰고는 쉽게 풀었습니다. 그 코드라도 공유해 드리겠습니다 : 

class Solution {
    public int addDigits(int num) {

        while (num >= 10) {
            int res = 0;
            while (num != 0) {
                res = res + num % 10;
                num /= 10;
            }
            num = res;
        }

        return num;
    }
}

 

코드에 설명이 필요 없을 정도로 쉬운 코드입니다. 요약해드리자면 이 코드는 주어진 정수 num의 자릿수를 반복적으로 더하여 한 자리 숫자가 될 때까지 계산하는 알고리즘을 구현한 것입니다. 이 방법은 루프를 사용하여 각 자릿수를 더하고, 그 결과를 다시 반복하는 방식입니다. 끝!

공간복잡도는 조건을 지켰지만, 시간 복잡도가 O(logn) 이라는 점...

---

이 문제를 조금 더 파헤쳐 보고자 사람들의 솔루션이랑 인터넷을 뒤져봤는데요, 수학적인 접근방식을 찾았습니다 !

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

 

코드를 분석하자면,

• 입력 값이 0인 경우:
  • num이 0이면 바로 0을 반환합니다.
• 입력 값이 0이 아닌 경우:
  • 1 + (num - 1) % 9 공식을 사용하여 디지털 루트를 계산하고 반환합니다.

저 %9 가 핵심입니다. 분명 수업시간 때 봤던 내용이었는데, 다 까먹고 이렇게 봐서야 떠오르니 제 기억력 때문에 씁쓸합니다.

---

내 코드 Runtime 결과