숫자 num이 주어졌을 때, 그 숫자를 이루고 있는 모든 자릿수의 합을 구하는 프로그램을 만들어 보겠습니다. 여기서 중요한 조건은 문자열(string)로 변환하지 않고 문제를 해결해야 한다는 점입니다.
예를 들어 입력값이 num = 512라면, 출력 결과는 8이 됩니다. 왜냐하면 5 + 1 + 2 = 8이기 때문입니다.
문제 해결 접근 방법
문자열을 사용하지 않고 자릿수의 합을 구하려면 나눗셈과 나머지 연산을 활용할 수 있습니다. 알고리즘은 다음과 같은 단계로 진행됩니다.
- 합계를 저장할 변수
sum을 0으로 초기화합니다. num이 0이 아닌 동안 아래 과정을 반복합니다.sum := sum + (num mod 10)— 10으로 나눈 나머지를 더해 마지막 자릿수를 추출합니다.num := num / 10의 몫 — 10으로 나눈 몫을 저장해 마지막 자릿수를 제거합니다.
- 반복이 끝나면
sum을 반환합니다.
구현 예제
아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
class Solution:
def solve(self, num):
sum = 0
while(num != 0):
sum = sum + int(num % 10)
num = int(num / 10)
return sum
ob = Solution()
print(ob.solve(512))입력
512
출력
8
코드 동작 원리 설명
위 코드가 어떻게 작동하는지 단계별로 살펴보겠습니다.
- 1단계:
num = 512,sum = 0으로 시작합니다. - 2단계:
512 % 10 = 2이므로sum = 0 + 2 = 2가 되고,num은51이 됩니다. - 3단계:
51 % 10 = 1이므로sum = 2 + 1 = 3이 되고,num은5가 됩니다. - 4단계:
5 % 10 = 5이므로sum = 3 + 5 = 8이 되고,num은0이 됩니다. - 5단계:
num이 0이 되었으므로 반복문이 종료되고 최종 결과8이 반환됩니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(log₁₀ n)입니다. 숫자의 자릿수만큼만 반복하기 때문에 매우 효율적입니다. 공간 복잡도 역시 추가 변수 하나만 사용하므로 O(1)입니다.
마무리
이처럼 나머지 연산(%)과 정수 나눗셈(// 또는 int())을 활용하면 문자열 변환 없이도 손쉽게 각 자릿수의 합을 구할 수 있습니다. 이 기법은 디지털 루트 계산, 하샤드 수 판별 등 다양한 수학 관련 코딩 문제에서 자주 활용되니 꼭 익혀두시기 바랍니다.