[파이썬] 프로그래머스 : 124나라의 숫자 (Lv.2)

[파이썬] 프로그래머스 : 124나라의 숫자 (Lv.2)

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

프로그래머스

---

 

풀이

0. 방향성 생각

3진법과 비슷하다는걸 알 수 있다.

1 2 3 : 1자리

4 ~ 12 (3+9) : 2자리

13~39 (12+27) : 3자리

자리수는 등비수열 합과 연관이있다. 숫자가 어느 구역에 있는지, 몇 번 째 자리수인지 찾는다

1. 구간 찾기

def solution(n):

    arr = [0]
    k = 1
    while arr[-1] < 5*10**7 :
        arr.append(arr[-1]+3**k)
        k += 1
    arr.append(arr[-1]+3**k)
    
    section = 0
    for i in range(len(arr)):
        if n > arr[i] : section = i
        else : break

등비수열의 합을 담은 arr을 만든다.

이후 몇 번 째 구간에 있는지 section을 얻는다.

 

2. 매핑, 변환

    n -= arr[section]+1 # 매핑 : section의 n번째 수
    s = ''
    while n:
        n,q = divmod(n,3)
        s = str(q) + s
    if len(s) < section+1 :
        s = (section+1-len(s))*'0'+s
        
    table = {'0':'1','1':'2','2':'4'}
    answer = ''
    for i in s:
        answer += table[i]
    return answer

각 수를 0부터 3**k-1의 수로 변환한다.

이 수를 3진법으로 변환한 수 자리수를 채워준다.

table을 통해서 124 숫자로 바꿔주면 정답

---

전체코드

def solution(n):

    arr = [0]
    k = 1
    while arr[-1] < 5*10**7 :
        arr.append(arr[-1]+3**k)
        k += 1
    arr.append(arr[-1]+3**k)
    
    section = 0
    for i in range(len(arr)):
        if n > arr[i] : section = i
        else : break

    n -= arr[section]+1 # 매핑 : section의 n번째 수
    s = ''
    while n:
        n,q = divmod(n,3)
        s = str(q) + s
    if len(s) < section+1 :
        s = (section+1-len(s))*'0'+s
        
    table = {'0':'1','1':'2','2':'4'}
    answer = ''
    for i in s:
        answer += table[i]
    return answer