프로그래머스 12931 - 자릿수 더하기 (Lv.1)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/12931

// 프로그래머스 12931 - 자릿수 더하기 (Lv.1)
// https://school.programmers.co.kr/learn/courses/30/lessons/12931

// 문제 설명
// 자연수 N이 주어지면 N의 각 자릿수의 합을 구해서 return 한다.
// N = 123이면 1 + 2 + 3 = 6.

// 제약 조건
// N의 범위: 100,000,000 이하의 자연수

// Example
// Input : 123   Output: 6
// Input : 987   Output: 24

// 접근 — 10으로 나누며 마지막 자리를 떼어낸다
// 1) n % 10 이 현재 마지막 자릿수, n /= 10 이 그 자리를 버린 수.
//    두 연산을 n이 0이 될 때까지 반복하면 모든 자릿수를 한 번씩 훑는다.
// 2) 반복 횟수는 자릿수 = O(log10 N). N 상한이 1억이라 최대 9회.
// 3) 자릿수합 상한은 99,999,999의 72 — int로 충분.
// to_string 후 c - '0'으로 더하는 방법도 같은 O(log10 N)이지만,
// 문자열 할당이 없는 나눗셈 방식을 기본으로 둔다.
// 시간 O(log10 N), 공간 O(1)

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int sum = 0;

    while (n > 0) {
        sum += n % 10;                    // 마지막 자릿수
        n /= 10;                          // 그 자리를 버림
    }

    return sum;
}

정리

• % 10과 /= 10은 한 쌍으로만 의미가 있다. % 10이 마지막 자리를 읽고, /= 10이 그 자리를 버린다. 둘 중 하나가 빠지면 같은 자리를 무한히 읽거나 자리를 건너뛴다. 나머지로 읽고 나눗셈으로 전진하는 이 골격은 진법 변환의 최소 형태이기도 하다 — 10 대신 3을 넣으면 68935 3진법 뒤집기의 분해부와 완전히 같은 코드가 된다.
• 복잡도는 N이 아니라 자릿수에 비례하는 O(log10 N)이다. 상한 1억이면 9회 — 입력 크기 자체는 커 보여도 루프가 한 자리 수준이라 성능 고민이 없는 문제. “N까지 훑는가, N의 자릿수만 훑는가”를 구분하는 습관이 그대로 12928 약수의 합의 O(n) vs O(√n) 판단으로 이어진다.
• 자료형 상한: 최댓값은 99,999,999의 자릿수합인 72. 자릿수합은 원본 수보다 압도적으로 작아 int 오버플로 위험이 없다. 반대로 자릿수합을 여러 번 반복 적용하면 한 자리로 수렴하는 성질(디지털 루트)이 있고, 이게 9로 나눈 나머지와 같다는 사실이 별도 계열 문제의 열쇠가 된다.
• 종료 조건은 n > 0이지 n >= 0이 아니다. >= 0으로 쓰면 n이 0일 때 0 / 10 == 0으로 값이 줄지 않아 무한 루프에 빠진다. 제약이 자연수라 0 입력 자체는 없지만, 조건은 입력 전제가 아니라 루프 자체의 안전성으로 고르는 게 변형 문제에서 안전하다.
• 문자열 변환 방식(to_string(n) + c - '0')도 같은 O(log10 N)이고 가독성은 오히려 좋다. 이때 c - '0' 변환은 문자 코드가 연속이라는 성질을 쓰는 것으로, 5622 다이얼·10809 알파벳 찾기에서 쓰는 c - 'A'와 같은 계열. 다만 이 문제는 힙 할당 없이 산술만으로 끝나므로 나눗셈 쪽이 더 단순하다.
• 자릿수합은 그 자체가 답인 경우보다 부품으로 쓰이는 경우가 많다 — 하샤드 수는 “원본이 자릿수합으로 나누어떨어지는가”라서 이 함수 위에 n % sum == 0 한 줄만 얹으면 끝난다.
• 검증: 예제 2개(6, 24)와 경계 케이스 — 최솟값 1(→ 1), 상한 100,000,000(→ 1), 자릿수합 최대 99,999,999(→ 72), 0이 섞인 1,000,000(→ 1) 통과 (MSVC /std:c++17 컴파일·실행).

핵심 요약 — % 10으로 마지막 자리를 읽고 /= 10으로 버리는 한 쌍이 자릿수 분해의 전부다. 복잡도는 N이 아니라 자릿수에 비례하는 O(log10 N)(상한 1억 → 9회), 자릿수합 최댓값은 72로 int 여유가 크다. 10을 다른 수로 바꾸면 그대로 진법 분해가 된다.