Happy Number

Q: 왜 이 과정은 항상 1에 도달하거나 루프에 빠질까요?

d 자리 숫자는 최대 81 × d 에 대응하므로 큰 수는 빠르게 작아집니다. 2^31-1 이하의 어떤 시작값이든 한 번의 단계 후에는 1000보다 작아지고, 1000보다 작은 수는 최대 243에 대응합니다. 이 과정에서 1000개 미만의 값만 거치므로 반드시 이미 나온 값을 다시 만나게 되고, 그때부터는 순환합니다. 1은 자기 자신에 대응하는 유일한 수입니다.

Q: Happy Number의 시간 복잡도는 얼마인가요?

첫 단계에서는 n 의 O(log n) 자릿수를 읽습니다. 이후의 모든 값은 1000보다 작고, 이 과정은 최대 20개의 수 안에서 반복되므로 전체 시간은 O(log n) 입니다. 해시 집합 버전은 방문한 수를 저장하고, Floyd 버전은 O(1) 의 공간을 사용합니다.

쉬움빠른 포인터와 느린 포인터 해싱

+10

양의 정수 n에서 시작해 각 자리 숫자의 제곱의 합으로 계속 바꿉니다. 예를 들어, 12는 1² + 2² = 5가 됩니다. 이 과정을 반복해 1에 도달하면 n은 행복수입니다. 그렇지 않으면 1을 포함하지 않는 숫자들 사이를 영원히 맴돕니다. n이 행복수이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

함수

isHappy(n: integer) → boolean

ninteger: 테스트할 양의 정수
반환값boolean: 숫자의 각 자릿수를 제곱해 더한 값을 반복했을 때 1에 도달하면 true, 무한 루프에 빠지면 false

제약 조건

1 ≤ n ≤ 2³¹-1

예제

입력: n = 7
출력: true
설명: 7은 49가 되고, 이어서 4² + 9² = 97, 다음은 130, 그다음은 10, 그리고 1이 됩니다. 과정이 1에 도달하므로 7은 행복수입니다.

입력: n = 2
출력: false
설명: 2는 4가 되고, 이어서 16, 37, 58, 89, 145, 42, 20이 된 다음 다시 4가 됩니다. 그 뒤로는 같은 여덟 숫자가 영원히 반복되며 1에 도달하지 않습니다.

입력: n = 100
출력: true
설명: 1² + 0² + 0² = 1이므로, 100은 한 단계 후에 1에 도달합니다.

제출 시 숨은 테스트 +16개

후속 질문

1부터 10^6까지의 행복수를 빠르게 세려면 어떻게 해야 할까요? 모든 시작 숫자부터 처음부터 다시 계산하는 대신, 1000보다 작은 숫자에 대한 답을 재사용할 수 있습니다.

힌트

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

3개 중 0개 열림

풀이

이 과정은 무한대로 계속될 수 없습니다. 10자리 숫자는 최대 10 × 81 = 810에 대응하고, 1000보다 작은 숫자는 최대 3 × 81 = 243에 대응하므로, 한 단계가 지나면 이 과정은 1000보다 작은 값들 안에 머물며 반드시 1에 도달하거나 숫자를 반복해야 합니다. 따라서 이 문제는 사이클 감지 문제로 바뀝니다. 이미 본 값을 기억하거나, 느린 이동자와 빠른 이동자를 실행해 둘이 만나는지 확인하면 됩니다.

지금까지 본 모든 숫자를 기억하세요

핵심 아이디어

수열을 따라가며 모든 숫자를 해시 집합에 저장하세요. 숫자 하나를 지나가기 전에 그 숫자가 이미 집합에 있는지 확인하세요. 2의 경우 집합은 2, 4, 16, 37, 58, 89, 145, 42, 20으로 채워지고, 다음 값은 4인데 이미 집합에 있습니다. 즉, 1에 도달하지 않은 채 순환이 닫혔으므로 2는 행복수가 아닙니다. 1에 도달하면 true로 탐색이 끝납니다.

다음 숫자는 현재 숫자에만 의존하므로 이것이 올바릅니다. 숫자가 다시 나타나면 그 뒤의 모든 값도 정확히 반복되므로 새로운 숫자는 나타날 수 없으며, 1에도 절대 도달하지 않습니다.

탐색은 짧습니다. 첫 단계에서는 n의 O(log n)개 자릿수를 읽고, 그 이후의 값은 모두 1000 미만입니다. 이때 1에 도달하거나 숫자가 반복되기 전까지 방문하는 서로 다른 숫자는 최대 20개입니다. 집합은 이 숫자들을 저장합니다. C 코드는 1000개의 항목으로 이루어진 플래그 배열을 집합으로 사용하며, 모든 값이 1000 미만이 되는 첫 단계 이후부터 기록을 시작합니다.

알고리즘

빈 해시 집합 seen을 만듭니다.
n이 1이 아닌 동안, n이 seen에 있으면 false를 반환합니다.
그렇지 않으면 n을 seen에 추가하고 n을 각 자릿수의 제곱의 합으로 바꿉니다.
루프가 끝나면 n은 1입니다. true를 반환합니다.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False  # back at an earlier number: a loop without 1
        seen.add(n)
        n = digitSquareSum(n)
    return True

빠른 보행자와 느린 보행자(Floyd의 사이클 탐지)

핵심 아이디어

각 숫자를 자릿수 제곱합을 가리키는 화살표가 하나 있는 노드라고 생각해 보세요. n에서 화살표를 따라가면 화살표가 다시 1을 가리키는 1에 도달하거나 루프에 빠집니다. 이는 사이클을 포함할 수 있는 연결 리스트의 형태이며, Floyd 알고리즘은 아무것도 저장하지 않고 사이클을 감지합니다. slow는 매 라운드마다 한 걸음씩, fast는 두 걸음씩 이동합니다.

루프에 1이 포함되어 있지 않으면 두 이동자는 모두 루프를 계속 돌게 되고, 매 라운드마다 fast가 slow보다 한 걸음씩 더 나아가므로 두 이동자 사이의 간격은 두 이동자가 같은 숫자에 설 때까지 1씩 줄어듭니다. 2의 경우 일곱 라운드 후에 42에서 만납니다. 이동 경로가 1에 도달하면 fast가 먼저 도달해 그 자리에 머뭅니다. 1의 자릿수 제곱합은 1이기 때문입니다. 그러므로 fast가 1이 되거나 두 이동자가 만날 때 중단하고, fast가 1인지 확인해 답을 구합니다.

7의 경우 slow는 7, 49, 97로 이동하고, fast는 49, 130, 1로 이동하여 fast가 1에 도달한 상태로 루프가 중단됩니다. 라운드 수는 이동 경로 길이의 작은 배수 이하이므로, 시간 복잡도는 집합을 사용하는 버전과 같고 메모리는 정수 두 개입니다.

알고리즘

숫자의 각 자릿수 제곱의 합을 반환하는 도우미 함수를 작성하세요.
slow = n으로 설정하고 fast를 n의 한 단계 다음 숫자로 설정하세요.
fast가 1이 아니고 slow와 fast가 다르면, slow를 한 단계 이동시키고 fast를 두 단계 이동시키세요.
fast가 1인지 반환하세요.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    slow = n
    fast = digitSquareSum(n)
    # fast moves two steps for every step of slow; they meet only inside a loop.
    while fast != 1 and slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    return fast == 1

함정과 경계 사례

숫자 연산은 간단합니다. 대부분의 실수는 루프가 언제 멈추는지에서 발생합니다.

다른 종료 조건 없이 값이 1이 될 때까지 반복하기. 2에서는 이 루프가 끝나지 않습니다.
같은 숫자에서 slow와 fast를 시작하고 첫 이동 전에 slow != fast를 검사하기. 루프가 실행되지 않아 7이 행복하지 않은 수로 나옵니다. fast를 한 단계 앞에서 시작하거나, 첫 비교 전에 둘 다 이동하세요.
Floyd 버전에서 slow == 1을 반환하기. fast가 먼저 1에 도달해 루프가 즉시 멈추는 동안 slow는 여전히 97에 있을 수 있습니다.
숫자의 제곱이 아니라 각 자릿수를 더하거나, 숫자 전체를 제곱하기. 12의 다음 값은 3도 144도 아닌 1² + 2² = 5입니다.
워커가 만날 때마다 n이 행복하지 않은 수라고 선언하기. 1은 자기 자신으로 매핑되므로 워커는 1에서도 만나게 됩니다. 어디에서 만났는지 확인하거나 fast가 1이 되자마자 멈추세요.

자주 묻는 질문4

왜 이 과정은 항상 1에 도달하거나 루프에 빠질까요?

d자리 숫자는 최대 81 × d에 대응하므로 큰 수는 빠르게 작아집니다. 2^31-1 이하의 어떤 시작값이든 한 번의 단계 후에는 1000보다 작아지고, 1000보다 작은 수는 최대 243에 대응합니다. 이 과정에서 1000개 미만의 값만 거치므로 반드시 이미 나온 값을 다시 만나게 되고, 그때부터는 순환합니다. 1은 자기 자신에 대응하는 유일한 수입니다.

Happy Number의 시간 복잡도는 얼마인가요?

첫 단계에서는 n의 O(log n)자릿수를 읽습니다. 이후의 모든 값은 1000보다 작고, 이 과정은 최대 20개의 수 안에서 반복되므로 전체 시간은 O(log n)입니다. 해시 집합 버전은 방문한 수를 저장하고, Floyd 버전은 O(1)의 공간을 사용합니다.

왜 불행한 수는 모두 결국 4에 도달할까요?

1000 미만의 모든 수를 확인해 보면 1을 피하는 루프는 정확히 하나입니다. 4, 16, 37, 58, 89, 145, 42, 20을 거쳐 다시 4로 돌아옵니다. 모든 시작값은 1000 미만으로 내려가므로, 행복하지 않은 모든 수는 이 루프에 빠집니다. 해결 방법은 4를 만나는 즉시 멈출 수 있지만, 이는 면접에서 근거를 설명해야 하는 사실에 의존합니다. 집합과 플로이드의 방법에는 그런 지식이 필요하지 않습니다.

Happy Number는 Linked List Cycle과 어떤 관련이 있나요?

둘 다 각 항목에서 화살표를 하나씩 따라갔을 때 이미 방문한 항목으로 돌아오는 경우가 있는지 묻습니다. Happy Number에서는 화살표가 각 자릿수의 제곱의 합이고, 연결 리스트에서는 다음 포인터입니다. 그래서 Floyd의 빠른 탐색자와 느린 탐색자는 두 문제를 모두 상수 메모리로 해결합니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

n = 7

기대값

true