[알고리즘] 프로그래머스 2단계 124 나라의 숫자

입출력 예 )

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

시간 초과 코드

def solution(n):

    num = 1
    
    while n:
        if '0' in str(num) or '3' in str(num) or '5' in str(num) or '6' in str(num) or '7' in str(num) or '8' in str(num) or '9' in str(num):
            num += 1
        else:
            num += 1
            n -= 1
            
    return str(num-1)

주어진 10진법 숫자 n으로 while문을 돈다.
num을 1로 시작했을 때, 1, 2, 4 외의 다른 숫자의 경우에는 num만 증가시키고 1, 2, 4의 경우에는 n의 개수도 함께 빼준다.

문제는 n이 500,000,000 이하의 자연수라는 것이다. 큰 수의 경우에는 5억번 반복문을 돌 수도 있으며 시간 초과가 나게 된다.

정답 코드

def solution(n):
    
    if n <= 3:
        return '124'[n-1]
    else:
        x, y = (n-1) // 3, (n-1) % 3
        return solution(x) + '124'[y]

시간 초과가 나지 않는 방법은 재귀 함수 를 이용하는 것이다.

10진법 수 1, 2, 3은 124 나라의 1, 2, 4가 된다.
이후 나머지 숫자들은 일정한 규칙을 가지고 증가하게 된다.

예를 들어 n이 10으로 주어졌다고 하자.
x = ( 10 - 1 ) // 3 = 3 이고 y = ( 10 - 1 ) % 3 = 0 이 된다.
solution(3) + '124'[0]은 '4' + '1' 이 되어 10을 124 나라의 숫자로 표현하면 41이 된다.