[코딩테스트] 프로그래머스 - 124 나라의 숫자 (Lv.2) in 파이썬 Python

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

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

예시:

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

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

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

풀이

- 문제에서 주어진 10진법 - 124나라 표기법에, 3진법을 표기법을 더해보자

- 124 나라에서는 세 가지 숫자로 표기하므로, 3진법과 관련있음을 알 수 있다.

 

- 표에서 보듯이, 3의 배수를 제외한 숫자들은 3진법 표기와 동일하다.

=> 124나라에서는 0이 없으므로,

=> 나머지 = 0으로 하고 자리올림 +1 할 것을,

=> 나머지 = 4로 생각하고 자리올림을 하지 않는 것이다.

 

- 따라서, n을 3진법으로 표기하되,

~> 나머지 = 0일 경우 (3의 배수),

~> 0대신 4를 집어넣고,

~> 몫에서는 1을 빼준다.

 

파이썬 구현

 

def solution(n):
    remainders = []

    q, r = divmod(n,3)
    while True:
        if r == 0:
            r = 4
            q -= 1
        remainders.append(r)
        if q < 1:  #몫이 0이하로 되면 loop종료
            break
        q, r = divmod(q, 3)

    remainders = remainders[::-1] # 역순으로 배열
    answer = ''.join (map(lambda x: str(x), remainders))
        
    return int(answer)

 

다른 분들의 풀이

- 멋진 풀이들이 많았다...!! 그 중 재귀함수를 이용한 풀이가 눈에 띄였다.

def solution(n):
	# n = 1, 2, 3일 때 예외처리
    if n <= 3:
    	return '124'[n-1]
        
    else:
    	q, r = divmod(n-1, 3)
        return solution(q) + '124'[r]

(n-1)을 해주는 이유는 위의 풀이 방식과 동일한 이유일 것이다.