[LeetCode] - 1837. Sum of Digits in Base K

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

--> https://leetcode.com/problems/sum-of-digits-in-base-k/description/

 

문제 : 

Given an integer n (in base 10) and a base k, return the sum of the digits of n after converting n from base 10 to base k. After converting, each digit should be interpreted as a base 10 number, and the sum should be returned in base 10.

---

Example 1 :

Input : n = 34, k = 6

Output : 9

Explanation : 34 (base 10) expressed in base 6 is 54. 5 + 4 = 9.

 

Example 2 :

Input : n = 10, k = 10

Output : 1

Explanation : n is already in base 10. 1 + 0 = 1.

 

Constraints :

• 1 <= n <= 100
• 2 <= k <= 10

---

이번 문제는 주어진 정수 n(10진수)와 기수 k를 기준으로 n을 k진수로 변환한 후, 변환된 각 자릿수의 합을 구하여 반환하는 문제입니다. 변환된 자릿수들은 모두 10진수로 해석하여 합을 구해야 합니다.

 

class Solution {
    public int sumBase(int n, int k) {
        int sum = 0;
        while (n != 0) {
            int digit = n % k;
            sum += digit;
            n /= k;
        }

        return sum;
    }
}

 

정말 기초적인 문제고, 수학적인 접근 방식이 요구되는 문제이기도 해서 초보자분들께 추천드리는 좋은 문제입니다. 솔직히 이 문제를 푸시면, 많은 다른 비슷한 문제들도 쉽게 푸실 수 있을 거라고 생각됩니다. 저렇게 항상 Digits 관련된 문제가 넘쳐나기 때문이기도 하죠.

 

코드를 간략히 설명드리자면 : 

1. 변수 초기화 :
   • sum 변수를 0으로 초기화합니다. 이 변수는 변환된 각 자릿수의 합을 저장합니다.
2. 10진수를 k진수로 변환 :
   • while 반복문을 사용하여 n이 0보다 큰 동안 계속 반복합니다.
   • n % k 연산을 통해 현재 자릿수를 구하고, 이를 sum에 더합니다.
   • n /= k 연산을 통해 n을 k로 나누어 다음 자릿수로 이동합니다.
3. 끝 !

• 시간 복잡도 : O(log_k(n))
  • n을 k진수로 변환하기 위해 필요한 반복 횟수는 n을 k로 나눌 때마다 1/k가 되므로, 총 반복 횟수는 O(log_k(n))입니다.
• 공간 복잡도 : O(1)
  • 추가적인 리스트나 배열을 사용하지 않고, 상수 공간만 사용합니다.

---

내 코드 Runtime 결과