[PG_12899/Python] 124 나라의 숫자

문제

12899번: 124 나라의 숫자

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

 

---

틀린 풀이

124 나라의 숫자가 중복 조합의 형태를 가지고 있다는 것을 발견했다. 124 나라의 숫자는 1의 자리수가 세 개, 2의 자리수가 9개, 3의 자리수가 27개, 즉 [3, 9, 27, 81, ... ] 과 같이 3의 제곱수 형태로 증가하기 때문에 내가 뽑을 숫자의 개수를 구하고(#1) 중복 순열을 구한 후 원하는 숫자를 택하는 형태(#2)로 코드를 구현했다.

from itertools import product

def solution(n):
    # 1. 숫자를 몇 개 뽑아야할지(cnt) 구한다.
    s, cnt = 0, 0
    while s < n:
        cnt += 1
        s += 3**cnt

    # 2. 중복 순열에서 원하는 숫자를 픽한다.
    nums = ['1', '2', '4']
    answer = ''.join(list(product(nums, repeat=cnt))[n - s - 1])
    return answer

결과는?

n = 500, 000, 000 이하의 자연수이기 때문에 효율성 테스트를 하나도 통과하지 못한다.

 

옳은 풀이

3진법을 사용하되, 나눠지는 수가 3의 배수인 경우를 특별 처리하는 방법을 이용했다. 예를 들어 10진법 3, 6, 9를 124 나라 숫자로 표현하는 방법은 다음과 같다. 

3의 124나라 숫자	6의 124나라 숫자	9의 124나라 숫자
str(3 // 3 - 1) + str(4)	str(6 // 3 - 1) + str(4)	str(9 // 3 - 1) + str(4)
4	14	24

def solution(n):
    answer = ''
    while n > 0:
        if n % 3 == 0:
            answer += str(4)
            n = n // 3 - 1
        else:
            answer += str(n % 3)
            n = n // 3
    
    return answer[::-1]  # 역순 리턴

먼저 나오는 숫자가 앞에 위치하게 되므로 마지막에 역순으로 리턴해준다.

 

---

참고

1. [프로그래머스] 124 나라의 숫자 / Python - 빠리의 택시 운전사

2. 다른 사람의 풀이