[Python] 프로그래머스 124 나라의 숫자

124 나라의 숫자

 

문제 설명

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

• 124 나라에는 자연수만 존재합니다.
• 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이하의 자연수 입니다.

---

입출력 예

n	result
1	1
2	2
3	4
4	11

풀이

굳이 이 풀이를 이해하기 보다는
아래의 다른 사람이 쓴 코드를 보고 이해하는 것이 문제 의도에도 맞고 다른 문제에 응용하기도 좋다.

n의  일의 자리 수 는 값이 1 증가할때마다 숫자가 바뀐다. 따라서 (n-1) % 3 으로 쉽게 구해줄 수 있다.

 십의 자리 수 는 값이 3 증가할때마다 ,  백의 자리 수 는 값이 9 증가할때마다 숫자가 바뀐다.

하지만  십의 자리 수 는 n = 4부터 3 증가할때마다,  백의 자리 수 는 n =13부터 9 증가할때마다

숫자가 바뀌므로 주의해야 한다.

 

따라서  십의 자리 수 는 ( (n-4) // 3 ) % 3 으로 구해줄 수 있고

 백의 자리 수 는 ( (n-13) // 9 ) % 3 으로 구해줄 수 있다.

 

자릿수가 늘어나는 숫자를 나열해보면 다음과 같다.

n = 4, 13, 40, 121 …

n에 1을 빼고 나열해보면 3, 3+9, 3+9+27, … 이므로 등비수열의 합 공식을 써보면 다음과 같이 나온다.

$$\frac{a(r^i-1)}{(r-1)} \Rightarrow \frac{3(3^i-1)}{(3-1)} \Rightarrow \frac{3(3^i-1)}{2}$$

 

이 아이디어를 가지고 코드를 작성해보면 아래와 같이 작성할 수 있다.

 

내가 쓴 코드

def solution(n):
    num = '124'
    n -= 1
    answer = num[n % 3]
    for i in range(1, n):
        sum = 3*(3**i-1)//2 # 등비수열 합공식
        if n >= sum: 
            answer = num[((n-sum) // 3**i) % 3] + answer
        else: break
    return answer

 

다른 사람이 쓴 코드

def change124(n):
    num = ['1','2','4']
    answer = ""

    while n > 0:
        n -= 1
        answer = num[n % 3] + answer
        n //= 3
        
    return answer

3진법과 달리 0이 없기 때문에 n -= 1 이 필요하다.