[프로그래머스]124 나라의 숫자 (python풀이)

이번 주 첫 문제인 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이하의 자연수 입니다.

 

입출력 예

 

input(n)	output(result)
1	1
2	2
3	4
4	11

 

이 문제는 빈출 문제 중 하나인 진법 문제입니다.

 

머리가 나빠서 패턴 찾는데 고생했습니다.

 

우선 3개의 숫자로 표현해야 하니 3진법으로 접근해야 함을 알 수 있습니다. 

 

10 진법 -> 3진법 변환은 다음과 같습니다.

1. 10진법 숫자를 3으로 나눌 수 없을 때까지 나눈다.
2. 아래에서부터 역순으로 나머지 값이 3진법으로 변환된 수이다. 

 

하지만 이 문제는 0, 1, 2로 이루어진 3진법이 아닌 1, 2, 4로 이루어진 3진법입니다. 

가볍게 생각해보면 3 -> 4로 대체하면 될 것 같지만 3진법은 3이 없으므로 0 --> 3으로 변환 --> 4로 변환 두 단계를 거쳐야 합니다. 

 

즉 3진법 기준으로 10 이 3이 되어야 하며 이 값이 4로 변환되어야 합니다.

그렇다면 10이 어떻게 3이 되는가가 이 문제의 핵심입니다.

 

먼저 3진법으로 변환할 때 나머지가 0인 경우 해당 값을 3으로 변환합니다. 그리고 몫에서 1을 빼줍니다. 

이렇게 구한 최종 3진수에서 3으로 저장된 값들을 4로 바꾸어 주면 완성입니다.

 

아래 그림은 패턴 파악을 위해 구해본 1~15까지의 014 숫자입니다. 

def solution(n):
    answer = ''
    rev_base = [] 

    while n > 0:
        n, mod = divmod(n, 3) # 나누며 몫과 나머지 구하기 
        
        if mod == 0 :
            mod = 3 # 나머지 0->3으로 변경
            n -= 1 # 몫 - 1
        rev_base.append(mod) # 나머지 순서대로 입력 (마지막에 뒤집어야 함)
       
    for i,char in enumerate(rev_base):
        if char == 3:
            rev_base[i] = 4
            
    answer = ''.join(map(str, rev_base[::-1]))
    return answer