[프로그래머스 연습]124나라의 숫자 - Python3

문제

https://programmers.co.kr/learn/courses/30/lessons/12899

코딩테스트 연습 - 124 나라의 숫자 | 프로그래머스

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

1. 124 나라에는 자연수만 존재합니다.
2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법	124 나라
1	1
2	2
3	4
4	11
5	12
6	14
7	21
8	22
9	24
10	41

 

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• n은 500,000,000이하의 자연수 입니다.

 

입출력

n	result
1	1
2	2
3	4
4	11

 

 

알고리즘

answer = []


def recursive(n):
    global answer
    print("answer: ", answer)
    print("\nn: ", n)

    if n == 1:
        answer.append("1")
        return

    if n == 2:
        answer.append("2")
        return

    if n == 3:
        answer.append("4")
        return

    else:
        temp = n % 3
        print("나머지인 temp: ", temp)
        if temp == 1:
            answer.append("1")
            recursive((n // 3))

        if temp == 2:
            answer.append("2")
            recursive((n//3))

        if temp == 0:
            answer.append("4")
            recursive((n//3) - 1)


def solution(n):
    recursive(n)
    answer.reverse()
    result = ""
    for ans in answer:
        result += ans

    return result


n = 18
print(solution(n))

설명

재귀를 활용했다. 재귀함수는 다음과 같이 동작한다. 

종료조건

1. n 이 1일 경우, answer에 1을 붙이고 종료한다. 
2. n이 2일 경우, answer에 2를 붙이고 종료한다.
3. n이 3일 경우, answer에 4를 붙이고 종료한다. 

파라미터

• n을 3으로 나눈 몫 재귀호출의 파라미터로 넘겨준다. 

종료하지 않을 시 동작

• n이 3보다 클 경우, 그 n을 3으로 나눈 나머지를 temp에 저장한다
• temp가 1인 경우, answer에 1을 append한다.
• temp가 2인 경우, answer에 2를 append한다.
• temp가 0인 경우, answer에 4를 append하고, n을 3으로 나눈 몫에서 1을 뺸 값을 파라미터로 재귀호출한다. 

밑줄친 부분이 가장 중요한데, 이 문제를 진법문제와 똑같이 풀려고 하면 안된다. 예로 들어 6을 124나라의 숫자로 변환한다고 할 때, recursive(6)을 호출하면 6을 3으로 나눈 나머지가 0이므로 , answer에는 4가 append하게 되고, recursive(2)를 재귀호출한다. 그럼 answer에 2를 append하고 재귀호출이 끝나고, answer에는 4, 2 가 들어있어서 이를 역순으로 나타내면 24가 된다. 

이를 해결하기 위해서, n이 3으로 나누어 떨어질 경우 n을 3으로 나눈 몫에서 1을 빼서 파라미터로 넘기는 것이다. 위의 예에서, recursive(6)을 호출하면 answer에 4를 append하고, recursive(1)을 호출한다. 그럼 answer에는 1이 append되고 함수가 종료되고, answer를 뒤집어보면 14가 되어 정답이 된다. 

이렇게 되는 이유는, 0,1,2 의 3진법이 아니라 1, 2, 4로 변환하는 문제이기 때문이다. 주어진 규칙에 따라 10진법의 수를 다른 수로 변환하는건 비슷하지만, 3진법을 변환하는 방법을 124나라의 숫자로 변환하려고 하면 오류가 생긴다는 뜻이다. 

 

 

결과

n = 18을 출력한 결과이다. 올바른 결과를 출력한다. 

 

후기

규칙을 찾는 문제인데 넘넘 어려웠다. 사실 왜 저 답이 올바르게 작동하는지 잘 모르겠다. 3의 배수일 때 문제가 생긴다는 점을 유심히 보다가, 6을 예로 든 것처럼 14가 나와야 할 것이 자꾸 24가 나오니까 몫을 넘겨줄 때 1을 빼서 넘겨줘보자 하다보니 답이 나왔다. 

역시 수학적이고 논리적이고 좀 그 뭐 그런 류의 머리통이 필요한거같다. 나는 그런게 1도 없으니깐 열심히 연습해야지
-ㅅ-