[Algorithms] 124 나라의 숫자.(프로그래머스 lv1)

문제 설명

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

소스 코드.

출처 - https://burningrizen.tistory.com/119?category=816215

def solution(n):
    answer = ""
    while n > 0:
        n, i = divmod(n, 3)
        if i == 0:
            n -= 1
        answer = '412'[i] + answer
    return answer

설명

우선 이 알고리즘 문제는 3진수의 표현이다.

3, 6, 9  -> 4, 14, 24로 표현되는데 이것에서 규칙을 찾을 수 있다.

3진수의 10(3) 을 124s 나라 4로 간주하면 된다.

124 나라 숫자 4는 3진수의 10이고 10진수의 3이다.

3진수 변환

- 10 ->101(3) , 7 ->21(3) , 6 ->20(3) 

여기서 중요한거는 3진수의 10이 4로 표현된다고 변환하는 것이다.

그럼 3진수의 012은 어떻게 변환 해야 하는가?

012 -> 412로 바꿔준 후 

3의 배수 일때는 진수 변환 루프를 1회 적게 하면된다.

4는 3진수 10 이기 때문에 10 -> 4 로 가려면 

루프를 한번 적게 돌려서 0 1 -> 0 -> 4로 변환 해줄 수 있다. 

ex)

6 - > 20(3진수) -> 3 + 3 -> 10 + 10 -> 14

9 ->  100 ->  10 + 10 + 10 -> 20 + 10   -> 24

10 -> 101 -> 100(40) + 1- > 41  

- 루프 한번 적게 하면 100 -> 40으로 변환 가능.

루프를 1회 적게 한다.

진수 변환

def conv(n, base, exp="0123456789ABCDEF", result=""):
    while True:
        n, r = divmod(n, base)
        result = exp[r] + result
        if not n:
            break
    return result

*divmod    

divmod(a, b)는 2개의 숫자를 입력으로 받는다. 그리고 a를 b로 나눈 몫과 나머지를 튜플 형태로 리턴하는 함수.

divmod(7, 3)

> (2, 1)

몫을 구하는 연산자 //와 나머지를 구하는 연산자 % 를 각각 사용한 결과와 비교해 보자.

7 // 3

> 2

7 % 3

> 1