Armstrong Number

Q: 암스트롱 수란 무엇인가요?

암스트롱 수는 자기애 수라고도 하며, 각 자릿수를 자릿수의 개수만큼 거듭제곱한 값의 합과 같은 수입니다. 153 은 1^3 + 5^3 + 3^3 = 153 이므로 암스트롱 수이고, 9474 는 9^4 + 4^4 + 7^4 + 4^4 = 9474 이므로 암스트롱 수입니다. 한 자리 수는 모두 해당합니다. d^1 = d 이기 때문입니다.

Q: 암스트롱 수는 몇 개 있나요?

10진법에서 양의 나르시시즘 수는 정확히 88개이며, 가장 큰 수는 39자리입니다. k 자리 수는 최소 10^(k-1) 인 반면 각 자리 숫자의 거듭제곱 합은 최대 k × 9^k 이므로 목록은 유한합니다. 61자리부터는 그 합이 결코 따라잡을 수 없습니다. 1과 10^9 사이에는 31개가 있습니다.

Q: 암스트롱 수를 확인할 때 왜 64비트 정수가 필요한가요?

입력값은 32비트에 들어가지만, 거듭제곱한 각 자릿수의 합은 숫자보다 몇 배 더 클 수 있습니다. 999999999 의 경우 9 × 9^9 = 3486784401 이며, 2^31-1 = 2147483647 보다 큽니다. 따라서 32비트 합계는 오버플로되므로, 합계와 거듭제곱 값에는 64비트 자료형을 사용하세요.

Q: 암스트롱 수인지 확인하는 시간 복잡도는 얼마인가요?

n 은 자릿수가 대략 log n 개이며, 여기서는 최대 10개입니다. 각 자릿수를 분리하고 각 거듭제곱 값을 10개 항목으로 된 표에서 찾으면 시간 복잡도는 O(log n) , 공간 복잡도는 O(1) 입니다. 각 자릿수마다 반복문으로 d^k 를 다시 계산하면 시간 복잡도는 O(log² n) 이 되지만, 이 크기에서는 여전히 빠릅니다.

입문수학과 시뮬레이션

+10

양의 정수는 각 자릿수를 자릿수의 개수만큼 거듭제곱한 값들의 합과 같을 때 암스트롱 수입니다. 153은 세 자리 수이고 1^3 + 5^3 + 3^3 = 153이므로 암스트롱 수입니다. n을 받아 암스트롱 수이면 true를, 그렇지 않으면 false를 반환하는 함수를 작성하세요.

함수

isArmstrong(n: integer) → boolean

ninteger: 테스트할 양의 정수
반환값boolean: n이 각 자릿수를 자릿수만큼 거듭제곱한 값들의 합과 같을 때 참

제약 조건

1 ≤ n ≤ 10⁹

예제

입력: n = 153
출력: true
설명: 153은 숫자가 3개이므로 각 숫자를 세제곱합니다: 1 + 125 + 27 = 153. 합이 원래 숫자가 되므로 답은 true입니다.

입력: n = 10
출력: false
설명: 10은 숫자가 2개이므로 각 숫자를 제곱합니다: 1 + 0 = 1이며, 이는 10이 아닙니다. 답은 false입니다.

입력: n = 9474
출력: true
설명: 숫자가 4자리이므로 거듭제곱은 4입니다: 6561 + 256 + 2401 + 256 = 9474, 숫자 자체이므로 답은 true입니다.

제출 시 숨은 테스트 +31개

후속 질문

1과 10^9 사이에는 암스트롱 수가 단 31개뿐입니다. 10억 개의 수를 하나씩 검사하지 않고 모두 나열할 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

정의는 알고리즘입니다. n의 자릿수를 세고, 각 자릿수를 그 자릿수만큼 거듭제곱한 다음, 결과를 더해 n과 비교합니다. 주의해야 할 점은 숫자에 있습니다. 지수는 고정된 3이 아니라 해당 n의 자릿수이며, 합은 32비트 정수의 범위를 초과할 수 있습니다. 999999999의 경우 합은 9 × 9^9 = 3486784401입니다.

문자열에서 숫자 읽기

핵심 아이디어

n의 십진수 문자열에는 필요한 두 가지가 모두 들어 있습니다. 문자열의 길이는 지수 k이고, 각 문자는 숫자입니다. 9474의 문자열은 문자 4개로 이루어져 있으므로 9^4 + 4^4 + 7^4 + 4^4를 더합니다.

각 문자를 다시 숫자로 바꾸고, k제곱한 뒤 누적 합계에 더합니다. 계산을 마친 합계가 n과 같을 때에만 n은 암스트롱 수입니다.

합계는 64비트 정수에 저장합니다. n은 32비트에 들어가지만 합계는 그렇지 않을 수 있습니다. 999999999의 경우 3486784401이 되어 32비트 한계인 2147483647을 초과합니다. 반복문을 사용해 k번 곱하여 거듭제곱을 계산하면 숫자 하나당 k단계가 걸리므로, k가 대략 log n일 때 검사의 시간 복잡도는 O(k²)입니다. 여기서는 곱셈이 최대 100번이며, 문자열에는 k개의 문자를 저장할 메모리가 필요합니다.

알고리즘

n을 10진수 문자열로 변환하고 길이를 k라고 합니다.
64비트 total을 0으로 설정합니다.
각 문자를 숫자 d로 변환하고, 부동소수점 거듭제곱을 호출하는 대신 정수를 곱하여 d^k를 total에 더합니다.
total이 n과 같은지 반환합니다.

def isArmstrong(n):
    digits = str(n)
    k = len(digits)
    total = 0
    for ch in digits:
        total += int(ch) ** k
    return total == n

숫자를 하나씩 분리하고 그 거듭제곱을 찾아보세요

핵심 아이디어

문자열 없이도 산술 연산만으로 같은 작업을 할 수 있습니다. m % 10은 m의 마지막 자릿수이고, 10으로 정수 나눗셈을 하면 그 자릿수가 없어지므로, 아무것도 남지 않을 때까지 10으로 나누는 루프는 자릿수를 셉니다. 9474는 947, 94, 9, 0이 됩니다. 네 단계이므로 k = 4입니다.

숫자는 10개뿐이므로, 무엇이든 더하기 전에 0부터 9까지의 d에 대해 powers[d] = d^k 테이블을 만드세요. 그러면 각 자릿수에 k번 곱하는 대신 조회 한 번만 하면 됩니다. 검사는 O(log n) 시간이 걸리며, 테이블 크기는 10으로 고정되어 있으므로 공간 복잡도는 O(1)입니다.

두 번째 루프는 자릿수를 다시 하나씩 떼어 내어 powers[m % 10]을 합계에 더합니다. 각 항은 0 이상이므로 합계는 줄어들지 않으며, n을 넘는 순간 답은 false입니다. 999999999의 경우 세 자릿수를 처리한 뒤에 이 조건이 성립합니다. 즉, 3 × 387420489 = 1162261467입니다. 테이블에는 여전히 64비트가 필요합니다. n = 10^9는 자릿수가 10개이고 9^10 = 3486784401이기 때문입니다.

알고리즘

복사본을 10으로 나누어 0이 될 때까지 반복하며 n의 자릿수를 세고, 그 개수를 k라고 합니다.
0부터 9까지 모든 숫자 d에 대해 64비트 정수로 powers[d] = d^k를 채웁니다.
n의 새로운 복사본을 다시 10으로 나누고, 각 단계에서 powers[m % 10]을 total에 더합니다.
total이 n을 초과하면 즉시 false를 반환합니다.
마지막 자릿수를 처리한 후 total이 n과 같은지 여부를 반환합니다.

def isArmstrong(n):
    # Count the digits: k is the exponent.
    k = 0
    m = n
    while m > 0:
        k += 1
        m //= 10
    # powers[d] = d^k for the ten possible digits.
    powers = [d ** k for d in range(10)]
    total = 0
    m = n
    while m > 0:
        total += powers[m % 10]
        if total > n:
            return False  # the total only grows
        m //= 10
    return total == n

함정과 경계 사례

공식은 간단하므로, 버그는 그 주변의 숫자에서 발생합니다.

지수가 3으로 고정되어 있습니다. 153과 370은 허용하지만 9474는 거부하며, 7^3 = 343이므로 1보다 큰 한 자리 숫자는 모두 거부합니다.
합계가 32비트입니다. 999999999의 자릿수 거듭제곱 합은 3486784401이며, 표 항목 9^10도 같은 숫자입니다. C에서는 이 오버플로의 동작이 정의되지 않으며, Java와 C#에서는 음수로 순환하고, Rust 디버그 빌드에서는 패닉이 발생합니다. long, long long 또는 i64를 사용하세요.
부동 소수점 거듭제곱입니다. C의 pow와 Java의 Math.pow는 double을 반환합니다. 일부 C 런타임은 5^2에 대해 24.999...와 같이 정수보다 조금 작은 값을 반환한 적이 있으며, 이를 형 변환하면 24로 잘립니다. 대신 반복문에서 정수를 곱하세요.
잘못된 값과 비교합니다. 자릿수 반복문은 n을 0까지 나누므로, 복사본으로 작업하고 합계를 원래 값과 비교하세요.
과학적 표기법입니다. R에서 as.character(1e9)는 문자 5개인 "1e+09"이므로, 문자열을 기반으로 하는 R 해법에서는 sprintf("%.0f", n)을 사용해 형식을 지정합니다.

자주 묻는 질문4

암스트롱 수란 무엇인가요?

암스트롱 수는 자기애 수라고도 하며, 각 자릿수를 자릿수의 개수만큼 거듭제곱한 값의 합과 같은 수입니다. 153은 1^3 + 5^3 + 3^3 = 153이므로 암스트롱 수이고, 9474는 9^4 + 4^4 + 7^4 + 4^4 = 9474이므로 암스트롱 수입니다. 한 자리 수는 모두 해당합니다. d^1 = d이기 때문입니다.

암스트롱 수는 몇 개 있나요?

10진법에서 양의 나르시시즘 수는 정확히 88개이며, 가장 큰 수는 39자리입니다. k자리 수는 최소 10^(k-1)인 반면 각 자리 숫자의 거듭제곱 합은 최대 k × 9^k이므로 목록은 유한합니다. 61자리부터는 그 합이 결코 따라잡을 수 없습니다. 1과 10^9 사이에는 31개가 있습니다.

암스트롱 수를 확인할 때 왜 64비트 정수가 필요한가요?

입력값은 32비트에 들어가지만, 거듭제곱한 각 자릿수의 합은 숫자보다 몇 배 더 클 수 있습니다. 999999999의 경우 9 × 9^9 = 3486784401이며, 2^31-1 = 2147483647보다 큽니다. 따라서 32비트 합계는 오버플로되므로, 합계와 거듭제곱 값에는 64비트 자료형을 사용하세요.

암스트롱 수인지 확인하는 시간 복잡도는 얼마인가요?

n은 자릿수가 대략 log n개이며, 여기서는 최대 10개입니다. 각 자릿수를 분리하고 각 거듭제곱 값을 10개 항목으로 된 표에서 찾으면 시간 복잡도는 O(log n), 공간 복잡도는 O(1)입니다. 각 자릿수마다 반복문으로 d^k를 다시 계산하면 시간 복잡도는 O(log² n)이 되지만, 이 크기에서는 여전히 빠릅니다.

Python

def isArmstrong(n):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

n = 153

기대값

true