[코딩 인터뷰] LeetCode - 202. Happy Number 무한루프에 빠져나오기 위해서 집합사용 Python

오늘은 알고리즘의 기초를 다지며 '행복한 숫자(Happy Number)' 문제를 풀어볼 거에요. 준비되셨나요? 시작해봅시다! 🧑‍💻

 

 

---

문제 설명: 행복한 숫자란 무엇일까요? 🤔

'행복한 숫자' 문제는 이렇게 시작해요. 어떤 양의 정수에서 시작해서, 그 숫자의 각 자릿수를 제곱한 후 합한 새로운 숫자로 바꿉니다. 이 과정을 반복했을 때, 결과가 1이 되면 그 숫자는 '행복한 숫자'라고 해요. 반면 1이 되지 않고 계속 반복되면 '행복하지 않은 숫자'죠. 😄 ↔️ 😔

 

문제보러가기

 

---

문제 풀어보기: 실제 코드로 만나는 행복한 숫자 🧑‍💻

 

이 코드는 숫자를 문자열로 변환하여 각 자리수를 분리한 후, 각 자리수를 제곱하고 그 합을 다시 계산하는 함수 get_next를 사용합니다. 그리고 중복을 체크하기 위해 seen이라는 집합을 사용하여 이미 계산한 숫자를 저장합니다. 숫자가 1이 될 때까지 또는 숫자가 무한 반복되는 순환에 빠질 때까지 계속 숫자를 변환합니다. 만약 숫자가 1이 되면 True를, 무한 순환에 빠지면 False를 반환합니다.

def is_happy(n):
    def get_next(number):
        return sum(int(x) ** 2 for x in str(number))

    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = get_next(n)
    
    return n == 1

# 예제 사용
print(is_happy(19))  # True를 출력해야 합니다.
print(is_happy(2))   # False를 출력해야 합니다.

---

알아야 할 개념: 숫자의 자릿수를 다루는 방법 🔢

1. 자리수의 분리와 제곱: 주어진 숫자 n의 각 자리수를 분리하고, 각각을 제곱한 후 이들을 합해야 합니다. 이를 위해 숫자를 문자열로 변환하고, 각 문자를 정수로 변환한 뒤 제곱하면 됩니다.
2. 루프 탐지: '행복한 숫자'를 찾는 과정에서 무한 루프에 빠질 위험이 있습니다. 루프를 탐지하기 위해 이전에 계산한 모든 숫자를 저장하고, 새로운 숫자가 이전에 나왔던 숫자와 같은지 확인해야 합니다.
3. 집합 사용: 무한 루프를 탐지하려면 이전에 나온 숫자들을 저장해야 하는데, 이를 효율적으로 관리하기 위해 파이썬의 set을 사용할 수 있습니다. set은 원소의 중복을 허용하지 않기 때문에, 이미 계산된 숫자를 빠르게 확인할 수 있습니다.
4. 재귀 대 반복: 이 문제는 재귀적으로도 해결할 수 있지만, 여기서는 반복문을 사용하여 해결합니다. 재귀를 사용하면 호출 스택이 너무 깊어져서 스택 오버플로우가 발생할 수 있습니다.
5. 종료 조건: 숫자가 1이 되면, 해당 숫자는 '행복한 숫자'이므로 True를 반환하고 함수를 종료합니다. 만약 숫자가 이전에 나왔던 숫자로 되돌아가면 무한 루프에 빠진 것이므로 False를 반환합니다.

---

행복한 숫자 문제를 해결하기 위해 우리는 숫자의 각 자리수를 제곱하여 더하는 과정을 반복합니다. 이 과정에서 숫자가 1에 도달하면 그 숫자는 행복하다고 할 수 있으며, 무한 루프에 빠지면 행복하지 않은 숫자입니다. 우리는 이 과정을 통해 숫자의 성격을 파악할 수 있으며, 루프를 탐지하기 위해 집합을 사용하여 이미 계산된 숫자들을 추적합니다. 이 문제를 해결함으로써 우리는 숫자의 내부 구조와 재귀적 사고를 이해하는 데 도움이 될 뿐만 아니라, 루프 탐지와 같은 중요한 알고리즘 기술도 배울 수 있습니다. 결론적으로, 행복한 숫자 문제는 프로그래밍 능력을 향상시키는 좋은 연습이 될 수 있습니다.