[python 문자열] 124 나라의 숫자 - 프로그래머스 Lv.2

문제 설명

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이하의 자연수 입니다.

---

입출력 예

 n                                                                 result

1	1
2	2
3	4
4	11

 

전략

-문제 접근

124 나라는 3진법과 유사하게 표현합니다. 하지만 3진법과 표현 방법이 완전히 다릅니다. 예를 들어, 12의 경우 3진법의 표현은 다음과 같습니다. 9+3 = 110(3) 으로, 3자리수로 표현됩니다. 하지만 124 나라의 경우 44(124)로 표현이 됩니다. 두 개의 표현 방법 모두 3과 관련이 되어 있다는 것은 명백하다는 것을 알 수 있습니다.

 

-풀이

124 나라의 경우 자릿수가 1자리일 때 표현가짓수는 3가지입니다. ex) 1, 2, 4

자릿수가 2자리일 때는 표현가짓수가 9가지입니다. ex) 11, 12, 14, 21, 22, 24, 41, 42, 44

즉, 자릿수가 n자리일 때 표현가지수는 3^n 개가 됩니다.

이로부터 알 수 있는 것은 해당하는 숫자의 자릿수가 몇자리나 되는지입니다. 예를 들면 4의 경우 4 - 3^1 - 3^0>= 0 이므로 4는 2자리 수라는 것을 알 수 있습니다. 13의 경우 13 - 3^2- 3^1 - 3^0 >= 0 이므로 13은 3자리 수라는 것을 알 수 있습니다. 

 

한편, 각 자리에 어떤 숫자(1,2,4)가 들어갈지도 알아내야 합니다. 경험적으로 시행착오를 겪어보았고 다음과 같은 규칙을 발견하였습니다. n을 124로 표현했을 때 자릿수-1 만큼 3의 제곱배를 계속해서 빼줍니다. 그러면 n을 124로 표현했을 때 자릿수에서의 순위가 나옵니다.

 

두자리수

n이 

4의 경우 4-3-1=0 

5의 경우 5-3-1=1

9의 경우 9-3-1=5

 

0 = 0*3^1 + 0*3^0 => 11

1 = 0*3^1 + 1*3^0 => 12

5 = 1*3^1 + 2*3^0 => 24

 

이를 통해 3의 제곱배 앞에 붙은 0, 1, 2에 따라 숫자가 1,2,4로 정해진다는 것을 알 수 있습니다. 

 

 

세자리수 

n이

13의 경우 13-9-3-1=0

17의 경우 17-9-3-1=4

24의 경우 17-9-3-1=11

 

0 = 0*3^2 + 0*3^1 + 0*3^0 => 111

4 = 0*3^2 + 1*3^1 + 1*3^0 => 122

11 = 1*3^2 + 0*3^1 + 2*3^0 => 214

솔루션

def solution(n):
    answer = ''
    count=0
    while n-3**count>=0:
        n=n-3**count
        count+=1
    
    for _ in range(count):
        remain = n % 3
        n = n //3
        if remain == 0:
            answer+='1'
        elif remain == 1:
            answer+='2'
        elif remain == 2:
            answer+='4'
        
    return answer[::-1]