[python] 프로그래머스 12899번: 124 나라의 숫자

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

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

 

[효율성에서 실패한 코드]

문제를 보자마자 백트래킹이 생각나서 백트래킹으로 풀어봤다. 

자리수를 기준으로 [1,2,4] 배열에 접근하는 방법을 떠올렸다.

자리수가 1일 때 [1], [2], [4]

자리수가 2일 때 [1,1], [1,2], [1,4], [2,1], [2,2], [2,4], [4,1], ]4,2], [4,4]에 접근한다. 

이렇게 쭉 찾다가 우리가 원하는 n에 대응하는 124숫자를 발견하면 if num == targetN:

check 변수를 통해 탐색을 종료하는 방식으로 구현해봤다.

하지만 정확성 부분에서는 모두 정답 처리됐지만 효율성 부분에서 실패했다.

def dfs(count, arr):
    global num, targetN, check, answer
    if check: return
    if len(arr) == count:
        num += 1
        if num == targetN:
            check = True
            answer = ''.join(map(str, arr))
        return
    
    for i in [1,2,4]:
        arr.append(i)
        dfs(count, arr)
        arr.pop()
        

def solution(n):
    global num, check, targetN, answer
    targetN = n
    check = False
    answer = ''
    num = 0
    for i in range(1, 500000000): # 1의 자리수부터 대입
        dfs(i, [])
        if check:
            return answer
    return answer

 

[정답인 코드]

재귀 함수를 이용해 통과한 다른 분의 코드를 가져왔다.

우선 종료 조건(base case)으로 함수의 매개 변수 n이 3이하일 때 배정된 숫자를('124'[n-1]) return 한다. 

파이썬 내장함수인 divmod(a, b)를 이용하여 몫(a//b)과 나머지(a%b)를 구한다.

나머지값을 '124' 문자열의 인덱스로 접근하여 1의 자리를 구하고 10의 자리 이상을 재귀로 구하는 풀이이다.

def change124(n):
    if n<=3:
        return '124'[n-1]
    else:
        q, r = divmod(n-1, 3) 
        return change124(q) + '124'[r]