[자료구조] [python] Down to Zero II

Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 

 

www.hackerrank.com/challenges/down-to-zero-ii/problem

Down to Zero II | HackerRank

 

    queue 자료형을 이용해서 문제를 풀지 않았다. 문제에 제시된 N의 크기의 list를 생성한 후, 2부터 값을 하나씩 보면서 가능한 곱의 값들을 최소값과 비교하며, 값을 업데이트 하는 식으로 풀었다. 다만, 7과 같이, 소수인 경우 7->6->5->4->3->2->1->0으로 0으로 값이 향해가는 것이 아니라, 7->6->3->2->1->0 으로, 6의 값에서는 6이 3*2로 구성될 수 있다는 점을 이용하여, 6->3으로 값이 이동될 수 있다. 

 

 

import os
import sys
import math 
#
# Complete the downToZero function below.
#



max_n = 10**6
precomputed_list = list(range(max_n+1))

for i in range(2, max_n+1):
    cur_val = precomputed_list[i]
    prev_val = precomputed_list[i-1]
    
    if cur_val > prev_val +1:
        precomputed_list[i] = prev_val +1
        cur_val = precomputed_list[i]
        
    for j in range(2, i+1):
        multiple = i*j
        if multiple > max_n:
            break
        init_val = precomputed_list[multiple]
        
        if init_val > cur_val+1:
            precomputed_list[multiple] = cur_val+1

def downToZero(n):
    if n<=3:
        return n
    
    return precomputed_list[n]