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

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

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

10진법을 124 나라의 수로 바꾸는 문제입니다. 이 문제에서 124 나라의 수는 오직 1, 2, 4만 존재합니다.

자료구조

십진수로 12까지 나타낸 124나라의 숫자를 담은 리스트를 만들었고 전역 변수로 선언했습니다. 그리고 편의를 위해서 맨 앞에 0 값을 넣었습니다.

나의 풀이

numbers : 124나라의 숫자를 저장한 데이터입니다. 십진수 13은 124 나라의 세 자리 숫자로 표시되기 때문에, 두 자리로 표현할 수 있는 최대인 12까지만 변환해서 담았습니다. 그리고 문제 풀이의 편의성을 위해서 0을 숫자 리스트 맨 앞에 추가했습니다. 이렇게 함으로써 numbers[i]는 십진수 i를 124 나라의 숫자로 표현한 값이 됩니다. 

위의 그림을 통해 1의 자리 수에 1, 2, 4가 계속 반복된다는 것을 알 수 있고, 1의 자리를 제외한 나머지 자리의 숫자는 이전에 나왔던 숫자와 같다는 것을 알 수 있습니다. 모든 10진수 숫자에서 1을 빼고 생각해보면 나머지 자리 숫자의 규칙을 알 수 있는데, 나머지 자리의 숫자는 (10진수 값 - 1) // 3 값에 해당하는 10진수의 124수와 같습니다.

따라서 점화식은 (n-1)//3 * 10 + [(n-1)%3 ==0이면 1, (n-1)%3 ==1이면 2, (n-1)%3 ==2이면 4]입니다.

작성한 코드 - 효율성 실패

numbers = [0, 1, 2, 4, 11, 12, 14, 21, 22, 24, 41, 42, 44]


def solution(n):
    global numbers
    if n >= len(numbers):
        tmp = [0 for _ in range(n-len(numbers)+1)]
        numbers = numbers + tmp

    answer = recursion(n)

    return str(answer)


def recursion(q):
    mod = [1, 2, 4]
    if not numbers[q]:
        tmp = recursion((q - 1) // 3) * 10 + mod[(q - 1) % 3]
        numbers[q] = tmp
    return numbers[q]

이 코드로는 정확성은 통과하지만 효율성은 실패합니다. n의 최대값은 500,000,000이고 이 값이 n으로 들어온다면, numbers의 길이가 500,000,000이 되기 때문에 효율이 매우 떨어집니다. 그래서 리스트의 길이를 늘리지 않고 문제를 푸는 방법을 더 생각해야 했습니다.

작성한 코드 - 통과

numbers = [0, 1, 2, 4, 11, 12, 14, 21, 22, 24, 41, 42, 44]


def solution(n):
    answer = recursion(n)
    return str(answer)


def recursion(q):
    mod = [1, 2, 4]
    if q >= len(numbers):
        tmp = recursion((q - 1) // 3) * 10 + mod[(q - 1) % 3]
        return tmp
    else:
        return numbers[(q-1)//3] * 10 + mod[(q - 1) % 3]

생각해보니 재귀함수의 특성을 사용하면 굳이 리스트의 길이를 늘릴 필요가 없었습니다. 그래서 리스트의 길이를 늘리지 않고, 함수의 조건문을 위와 같이 바꿨습니다.

느낀 점

DP문제는 확실히 점화식만 잘 찾으면 어떻게든 풀 수 있는 것 같습니다. 항상 겁먹은 게 DP문제인데, 너무 어렵게 생각하지 말고 종이에 차근차근 써나가니 규칙을 발견할 수 있었습니다.

그리고 입력의 최대값을 조금 더 생각했다면, 구현할 때 숫자를 담은 리스트의 길이를 입력값만큼 늘리는 생각은 하지 않았을 것입니다. 앞으로 문제를 풀 때는 코드를 작성하기 전에 엣지케이스를 조금 더 생각해야겠습니다.