[프로그래머스] 124 나라의 숫자 - 파이썬

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

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

문제 설명

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

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

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

 

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

 

문제 풀이

3진수가 증가하는 것과 비슷한 과정으로 증가한다. 10진수에 해당하는 124진수와 몇 가지 수에서 3으로 나눈 몫과 나머지를 아래에 나열했다. nums = ['4', '1', '2'] 로 설정한다.

 

1: 1
2: 2
3: 4 -> 1 0

4: 11 -> 1 1
5: 12
6: 14 -> 2 0

7: 21
8: 22
9: 24 -> 3 0

10: 41
11: 42
12: 44 -> 4 0

13: 111 -> 4 1 
14: 112 -> 4 2

 

n이 최대 5억이므로 순차적으로 탐색하는 과정으로는 절대 해결할 수 없고 반드시 규칙(패턴)을 찾아야한다.

진수문제는 보통 n진수로 나는 목과 나머지를 활용하여 문제를 해결할 수 있다.

 

1, 2, 3 을 먼저 보면 3으로 나눠서 몫은 0 나머지는 각각 1, 2, 0 인데 나머지 1, 2, 0에 124진수 1, 2, 4가 대응된다는 것을 알 수 있다.

 

이제 몫이 1보다 큰 수 5를 보면, 5를 3으로 나눴을 때 몫은 1 나머지는 2이다. 몫이 0보다 큰 경우는 다시 그 몫을 3으로 나눠 몫과 나머지를 구한다. 1을 3으로 나누면 몫은 0 나머지는 1이다. 따라서 5는 나머지로 2, 1 가지므로 1-> 1 2 -> 2 즉 124진수로 12가 되어야 한다.

 

여기서 주목해야 할 점은 3의 배수인 숫자들이다. 3의 배수인 숫자 6를 예를 들어보자. 6은 3으로 나눴을 때 몫이 2 나머지가 0이다. 3의 배수인 수들을 나열해 보면 3으로 나눈 몫이 0보다 클 때, 몫에 1을 빼서 다시 3으로 나눈 과정을 반복해야한다는 점을 알 수 있다. 6 -> (2, 0) -> 1%3 = 1, 따라서 6은 나머지로 0과 1를 차례로 가진다.

그러므로 6은 124진수로 14임을 알 수 있다.

 

요약하면

1. n이 3의 배수인 경우

2. n이 3의 배수가 아닌 경우

2가지 경우로 나눠서 해결할 수 있다.

def solution(n):
    nums = ['4', '1', '2']
    s = ''
    answer = 0
    while True:
        q = n // 3
        r = n % 3
        
        if r == 0:
            q = q - 1
            
        s = s + nums[r]
        
        n = q
        if q == 0:
            break
    
    answer = s[::-1]
    return answer