[Python] 124 나라의 숫자

 

 

 

programmers.co.kr/learn/courses/30/lessons/12899

코딩테스트 연습 - 124 나라의 숫자

10진수를 문제에서 정의한 '124 나라의 숫자'로 변환하는 문제입니다.

 

문제를 처음 봤을 때 DP 문제라고 생각했다가(ㅠㅠ) 감이 잡히지 않아 타 블로그에서 3진법이라는 키워드를 얻었습니다.

 

3진법	10진수	124나라의 숫자
1	1	1
2	2	2
10	3	4
12	4	11
20	5	12
21	6	14
22	7	21
100	8	22
101	9	24

실제 문제풀이에서는 10진수 기준으로 13까지 적어봤으며, '4'를 '3'으로 바꿔보기도 했습니다.

그러던 도중 3진법에서 0이 등장할 때 124나라의 숫자에는 4가 등장하고, 숫자가 묘하게 바뀜을 알 수 있었습니다.

 

11을 타겟으로 3진법 변환을 해보며 0이 등장할 때 0을 4로 바꿔버리고, 그 다음에 나오는 1을 지우기 위해 피제수를 -1 연산하여 알고리즘을 도출할 수 있었습니다.

 

아래는 제출한 코드입니다.

def solution(n):
    answer = ''
    
    while n>=1:
        tmp = n%3
        if tmp == 0:
            answer += '4'
            n -= 1
        else:
            answer += str(tmp)
            
        n //= 3

    answer = answer[::-1]
    return answer

---

다른 풀이 1

def solution(n):
    answer = ''
    while n > 0:
        n -= 1
        answer = '124'[n%3] + answer
    return answer

3진법을 기준으로 0일때는 1, 1일때는 2, 2일때는 4로 만들어주기 위해 사전에 피제수에 -1을 한 풀이다. 

 

 

다른 풀이 2

def solution(n):
    if n<=3:
        return '124'[n-1]
    else:
        q, r = divmod(n-1, 3)
        return solution(q) + '124'[r]

재귀를 이용한 방법.