124 나라의 숫자

프로그래머스 - 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이하의 자연수 입니다.

입출력 예

n	result
1	1
2	2
3	4
4	11

접근

문제에서 제시한 예를 보면, 3진법의 규칙과 유사한 방식이라는 것을 금방 떠올랐다. 3으로 나누어 떨어져 0으로 들어가야 하는 자리에 4가 들어갈 뿐이다.

해결 과정

1. 나머지를 활용하면 어떨까?
   예를 들어, 8의 경우 3으로 나누면 몫은 2, 나머지는 2다.
   9의 경우에는 3으로 나누면 몫은 3, 나머지는 0이다.
   나머지가 0인 경우에만 4로, 1이나 2는 그대로 사용하면 124 나라의 규칙에 맞게 문자를 만들 수 있지 않을까?

2. 몫도 활용할 수 있지 않을까?
   10을 124 나라의 규칙에 맞게 변화시키면 41이다.
   10을 3으로 나누면 몫은 3, 나머지는 1이다.
   3을 124 나라의 규칙에 맞게 변화시키면 4다.

다른 사람의 풀이

여기까지 접근했지만, 위 방법을 어떻게 하면 코드로 구현할 수 있을지는 생각나지 않았다. 그래서 다른 사람의 풀이를 확인했다.

def solution(n):
    if n < 4:
        return "124"[n - 1]
    else:
        div, mod = divmod(n - 1, 3)
        return solution(div) + "124"[mod]

내가 미처 생각하지 못한 부분은 바로 n을 그대로 나누는 것이 아니라 n - 1을 나누는 것이었다.

몫을 활용할 때 n의 몫을 그대로 사용하면 예외가 발생할 수 있다.

• 12를 124 나라의 규칙에 맞게 바꾸면 44다.
• 12를 3으로 나눈 몫은 4다.
• 4를 124 나라의 규칙에 맞게 바꾸면 11이다.

하지만, n에서 1을 빼게 되면 위 예외도 해결할 수 있고, 다른 정상적인 경우도 아무 영향 없이 동작할 수 있게 된다.