프로젝트들/코딩 테스트

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

코곰 2021. 2. 15. 10:57

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 나라의 숫자

 

programmers.co.kr

풀이

- 문제에서 주어진 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)을 해주는 이유는 위의 풀이 방식과 동일한 이유일 것이다.