LeetCode [258]: Add Digits

📌 LeetCode [258]: Add Digits

🔗 문제 링크

---

문제 설명 📄

주어진 정수 num에 대해, 모든 자릿수를 더한 값을 계산하여 새로운 숫자를 만듭니다. 이 과정을 자릿수의 합이 한 자리 숫자가 될 때까지 반복합니다.

---

문제 해결 접근 🧩

1. 자릿수 합 계산:
   • 숫자를 문자열로 변환하여 자릿수를 추출.
   • 자릿수를 반복적으로 더하여 새로운 숫자를 생성.
2. 조건 반복:
   • 결과가 한 자리 숫자가 될 때까지 위 과정을 반복.

---

Solution 💻

class Solution:
    def addDigits(self, num: int) -> int:
        while num > 9:
            answer = 0
            for i in str(num):
                answer += int(i)
            num = answer

        return num

시간 복잡도 분석 ⏲️

• 숫자 변환 및 자릿수 합 계산:
  • 각 반복에서 O(d), 여기서 d는 자릿수의 개수.
  • num의 값이 줄어들므로, 반복 횟수는 로그에 비례 (O(log(num))).
• 최종 시간 복잡도: O(d * log(num)).

공간 복잡도 분석 🗄️

• 숫자 변환 및 계산: O(1).
• 총 공간 복잡도: O(1).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0
        return 1 + (num - 1) % 9

리팩토링 후 시간 복잡도 ⏲️

• 단일 계산: O(1).

리팩토링 후 공간 복잡도 🗄️

• 추가 공간 사용 없음: O(1).

---