[ Level 2 ] 124 나라의 숫자 - 파이썬

문제 설명

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

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

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

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

---

10진법을 124 나라 숫자로 바꾸면 1,2,4를 차례로 점점 product 하는 규칙임을 알 수 있다.

예를들어 1,2,3은 각각 repeat=1로 한 product이고,

3부터는 repeat=2로 한 product 연산 결과이다.

 

따라서, 3**1 + 3**2 + ... 으로 숫자가 점점 많아지므로 주어지는 숫자 n을 124 나라 숫자로 바꾸려면 우선 repeat이 몇번째에 해당하는지를 알아야한다.

 

이를 바탕으로 구현해보면 다음과 같다.

from itertools  import product
def solution(n):
    answer = ''
    
    s = ('1','2','4')
    i, tmp = 1, 0
    while True:
        tmp += 3**i
        if tmp >= n:
            break
        i += 1
    tmp1 = n - tmp
    answer = list(product(s, repeat = i))
    
    
    return ''.join(answer[tmp1-1])

 

하지만, 이 코드는 정확성은 다 맞지만 효율성 테스트에서 시간 초과로 점수를 받지 못했다.

 

다음 블로그를 확인했을 때, 다른 방법이 있다는 것을 확인했고 이런 생각을 하는 것에 놀라웠다,,

더 연습해서 이런 아이디어를 잘 낼 수 있도록 노력해야겠다.

 

위의 블로그에 나와있는 소스코드는 아래와 같다.

def solution(n):
    answer = ''
    while n:
        if n % 3:
            answer += str(n % 3)
            n //= 3
        else:
            answer += "4"
            n = n//3 - 1
    return answer[::-1]

 

 

Reference

https://latte-is-horse.tistory.com/127