‘얼른 마스크’씨 회사 전기 자동차의 행복한 일련번호

마스크를 쓰지 않고는 밖을 다니면 안 되는 코로나19 시대입니다.
코로나19가 장기화되면서 코로나 블루라는 말이 나올 정도로 우울한 사람들이 많아지고 있습니다.

세계적인 전기자동차 회사 경영자인 **‘얼른 마스크’**씨는
자신의 전기자동차를 타는 고객들이 조금이라도 행복할 수 있기를 바라며
판매하는 전기자동차 번호판 일련번호 4자리를 **행복 수(happy number)**로 채우고자 합니다.

행복 수는 각 자릿수의 제곱의 합으로 변환하는 과정을 반복할 때 언젠가는 1에 도달하는 수입니다.
예로, 13 → 1x1 + 3x3 = 10 → 1x1 + 0x0 = 1이므로 13은 행복 수입니다.

행복 수가 아닌 것은 슬픈(sad) 수 또는 불행(unhappy) 수라고 불립니다.
예로, 4 → 4x4 = 16 → 1x1 + 6x6 = 37 → 3x3 + 7x7 = 58 → … → 4 로 순환하여 결코 1에 도달할 수 없으니 4는 슬픈 수입니다.

문제

‘얼른 마스크’씨 회사 전기자동차의 일련번호가 될 수 있는 1 ~ 9999 범위의 행복 수는 모두 몇 개이고
그 총합은 얼마인지 구하는 프로그램을 작성해서 보내주세요 작성하세요.

입력

각 범위의 최댓값을 한 줄에 하나씩 입력으로 받습니다. 최종적으로 구하고자 하는 범위의 최댓값은 9999이므로 소스코드 안에 하드코딩 해도 됩니다.

9 99

출력

범위와 행복 수의 개수 그리고 총합을 아래와 같이 출력합니다.

1 ~ 9 범위의 행복 수는 2개이고 총합은 8입니다. 1 ~ 99 범위의 행복 수는 19개이고 총합은 924입니다.

참고

프로젝트 오일러 92번은 행복 수에 대한 조금 더 어려운 문제입니다.
https://euler.synap.co.kr/problem=92

출처) 사이냅소프트 채용퀴즈

문제 풀이

def practice_recursive(value, number_sheet, first_value):
    if number_sheet[value][0] == 1 and number_sheet[value][1]:
        return 1
    elif number_sheet[value][0] < 10 and number_sheet[value][0] != 0 and not number_sheet[value][1]:
        return number_sheet[value][0]
    else:
        target_string = str(value)
        total_number = 0
        for char in target_string:
            target_number = int(char)
            target_number *= target_number
            total_number += target_number
        if total_number > 9:
            total_number = practice_recursive(total_number, number_sheet, first_value)
        if total_number <= 9 and total_number != first_value and number_sheet[total_number] == 0:
            total_number = practice_recursive(total_number, number_sheet, first_value)
        return total_number


def happy_recursive(value, number_sheet, first_value):
    if number_sheet[value][0] != 0:
        return
    value_string = str(value)
    total_number = 0
    for char in value_string:
        target_number = int(char)
        target_number *= target_number
        total_number += target_number

    try:
        if total_number > 9:
            total_number = practice_recursive(total_number, number_sheet, first_value)
        if total_number <= 9 and total_number != first_value:
            total_number = practice_recursive(total_number, number_sheet, first_value)
    except RecursionError:
        number_sheet[value] = [first_value, False]
    else:
        if total_number == 1:
            number_sheet[value] = [1, True]
        elif total_number == first_value:
            number_sheet[value] = [total_number, False]
        elif total_number != first_value and number_sheet[total_number][1].__eq__(False) and total_number != 0:
            number_sheet[value] = [total_number, False]


k = int(input())

happy_number_sheet = dict()
for i in range(1, 10000):
    happy_number_sheet[i] = [0, False]

happy_number_sheet[1] = [1, True]

total_happy_number = 0
happy_number_counter = 0

for i in range(1, k + 1):
    happy_recursive(i, happy_number_sheet, i)
    if happy_number_sheet[i][0] == 1 and happy_number_sheet[i][1]:
        total_happy_number += i
        happy_number_counter += 1

for i in range(1, k + 1):
    print(i, ":", happy_number_sheet[i])

print(total_happy_number)
print("count : ", happy_number_counter)
print(total_happy_number * happy_number_counter)
  • 구현함에 어떻게 구현하면 좋을까? 라는 고민을 많이 했다.
  • 우선 한 가지 확실한 건, 행복한 수의 조건은 명확하고, 그 외에는 사실상 알아서 결정 해야 한다는 점이었다.
  • 따라서 행복수의 조건을 명확히 하면서, 연산의 과정에서 어떻게 문제가 발생하거나, 행복 수와 반대되는 개념들의 특징을 어떻게 명확히 할지를 생각해보았다.

로직 & 풀이 과정

  1. 핵심은 행복한 수의 조건(자기 자리수 전체를 분해, 각각 제곱해서 1이 나오는가?)이 나올 때까지 반복하는 부분(재귀로 표현 가능)
  2. 그렇다면 그 외의 경우는 어떤게 있는가?
    1. 자기 자신으로 돌아오는 경우
    2. 자기 자신의 숫자는 아니지만, 자기 외의 숫자로 반복되는 경우
  3. 2번의 경우를 해결하기 위한 해결은 어떻게?
    1. 우선, 연산을 기록할 수 있도록 dict 타입으로 각 숫자 별 행복수 결과를 기록할 수 있도록 했다. (최적화)
    2. 재귀의 특성 상 기존의 결과들을 거슬러서 기록하거나 하는 구조가 불가능하다. 따라서, 최적화가 될 수 있고, 이미 기록된 값들은 빠르게 연산될 수 있기 때문에 재귀 스택이 가득 차서 예외 처리가 발생할 때 무한하게 발동되는 구조니, 해당 값은 행복 수가 될 가능성이 없다고 판단. 이를 캐칭하기 위한 try-catch 문을 도입했다.

결과

C:\Python312\python.exe C:\Users\ryuax\workspace\2024-study-algorithm\synap_coding\01_얼른마스크.py 
9
1 : [1, True]
2 : [4, False]
3 : [4, False]
4 : [4, False]
5 : [4, False]
6 : [4, False]
7 : [1, True]
8 : [4, False]
9 : [4, False]
8
count :  2
16

C:\Python312\python.exe C:\Users\ryuax\workspace\2024-study-algorithm\synap_coding\01_얼른마스크.py 
99
1 : [1, True]
2 : [4, False]
3 : [4, False]
(중략 . . .)
96 : [4, False]
97 : [1, True]
98 : [4, False]
99 : [4, False]
924
count :  19
17556