[Programmers] Python_124 나라의 숫자

문제

 

문제 설명

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

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

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

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

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

 

제한사항

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

 

코드

def solution(n):
    T = "0124"
    #n이 3이하라면 n위치에 있는 T값을 return
    if n <= 3:
        return T[n]
        
    q, r = divmod(n, 3) #몫, 나머지
    #몫이 0일때는 n이 3이하라는 뜻이므로 q == 0일때 조건문은 만들지 않는다
    #나머지가 0이면 3으로 나누어 떨어진다는 뜻이므로 맨 마지막 숫자가 4가 되고 이후에 몫 - 1을 재귀호출
    if r == 0:
        return solution(q - 1) + "4"
    #나머지가 0이 아니라면 일반 진법 변환과 같이 진행한다
    else:
        return solution(q) + T[r]

 

진행 과정

 

예제 #1

n = 8

 

n = 1일때 1, n = 2일때 2, n = 3일때 4이므로 어떠한 값이 1, 2, 3이냐에따라 "1" 또는 "2" 또는 "4"가 된다. 그리고 이 어떠한 값을 구하는게 문제이다.

 

먼저 일반적인 진법 변환에서 사용하는 코드를 보자.

def change(n, out):
    T = "0123456789ABCDEF"
    q, r = divmod(n, out)
    if q == 0:
        return T[r]
    else:
        return change(q, out) + T[r]

보시다시피 변환될 숫자, 문자를 T에 저장에 놓고 나머지 값에 위치한 값을 뒤에 붙여나가는 식으로 진행된다.

 

그럼 이 문제에서도 T에 "124"를 저장해놓자. 아... index 1일때 1이 되어야되는데 2가 되버린다. 그럼 그냥 맨 앞에 아무거나 붙여서 index를 맞춰버리자.

T = "0124"

 

그러면 이제 나머지가 1이면 1, 2면 2, 3이면 4로 나오게 만들 수 있다. 어? 그런데 나머지가 3이 나올 수가 있나??

 

3으로 나누는데 나머지가 3이 나올리가 없다... 나머지가 0이 될 것이다.

 

우선 n이 3이하일때는 그대로 n에 위치한 값을 return하면 된다. 그리고 나머지가 0일때와 아닐때는 구별하여 return을 따로 구현해주어야한다.

 

나머지가 0이 아닐때는 나머지가 1이거나 2일때 밖에 없으므로 일반 진법 변환과 같은 방법으로 return하면된다. 하지만 나머지가 0일때는 잘 생각해봐야한다. 나머지가 0이라는 것은 해당 n값이 3의 배수라는 뜻이다. 즉, 3번째에 위치한 값이면 항상 마지막 값이 "4"가 될 것이다. 그리고 이후에는 몫 - 1값을 재귀 호출하여 진행하면된다.

 

몫 - 1을 재귀 호출하는 것이 어떻게 나왔냐면 1부터 10까지 진행해보았을때 규칙이 이렇게 나왔기 때문이다.

 

코드 진행은 다음과 같다.

 

1) T[n] = 2
2) solution(q) + T[r] = 22

3) T[n] = 2 #solution(q) 의 값

 

예제 #2

n = 9

 

이것도 예제 #1과 같이 진행하면 다음과 같다.

 

1) T[n] = 2
2) solution(q - 1) + 4 = 24

3) T[n] = 2 #solution(q - 1) 의 값