글 읽기 - 파이썬코드 시간초과.. 어떻게 줄일수있을까요

jmkim93 3년 전 0

알고리즘을 대략 설명드리자면

예를들어 87432 과 같은 감소수를 가정할 때, 1의자리부터 상위자리수의 숫자와 비교하며 1씩 차이나는지 비교한 후

상위자리수와의 차이가 1일 경우: 해당 자리수에서 숫자를 증가시켰을 때 감소수를 만들 여지가 없으므로 상위 자리수로 이동
상위자리수와의 차이가 1보다 클 경우: 해당 자리수의 숫자를 +1 해주는 방식입니다.

87432의 경우 1의자리, 10의 자리수에서는 증가시키지 못하고 100의 자릿수에서 증가시킬 수 있으므로

87432 -> 87/4/32로 나눈 후 87/5/10 -> 87510 와 같이 다음 감소수를 구할 수 있을 것 같습니다.

예외로 n자리 수 중에서 가장 큰 감소수같은 케이스인 (e.g. 98765) 경우 (n+1)자리 수 중 가장 작은 감소수 (e.g. 543210)를 쉽게 얻을 수 있습니다.

그리고 시간단축을 위해 계산한 값은 메모리에 저장해두는 방식을 쓰기도 했는데..

어떻게 더 시간단축을 할 수 있을지 모르겠습니다 ㅜ

(실제로 제 컴에서 돌릴때는 가장 큰 경우인 1022번째 9876543210도 64ms 안에 값이 나오구요..)

dict_next_dec_num = {1:2, 2:3, 3:4, 4:5, 5:6, 6:7, 7:8, 8:9, 9:10, 10:20, 20:21, 21:30, 30:31, 31:32, 32:40} 

#감소수 n이 주어졌을때 다음에 나오는 감소수를 반환하는 함수
def next_dec_num(n):
    if n in dict_next_dec_num:
        return dict_next_dec_num[n] #이미 계산했던 케이스면 메모리에서 꺼내옴
    else: #새로 구해야할 경우
        num_digit = len(str(n)) # n의 자릿수. e.g. n = 86432 이면 5
        n_arr = [int(str(n)[ii]) for ii in range(len(str(n)))] #각 자리수를 arr로 변환. e.g. [8, 6, 4, 3, 2]
        
        # 위 예시에서는 86432 다음 오는 숫자는 86510이 되는데, 이때 기준은 86/4/32 로 나눈뒤 86/5/10 을 반환하는 방식.
        # 이때 백의자리 4가 기준이 되는 이유는 1의자리부터 비교할 때 2->3, 3->4은 모두 1 차이밖에 안나기 때문에 올릴 수 없지만
        # 4->6은 2가 차이나서 4를 5로 바꿔도 감소수를 만들 수 있음
        # 아래의 j는 몇번째 자리에서 +1을 해줄지 for문으로 비교해가면서 구함.
        
        j = 0
        for i in range(num_digit-1):
            if n_arr[-1-i]+1 == n_arr[-1-(i+1)]: # 1만큼 차이나면 자리수를 올림
                j += 1
            else:
                break #그렇지 않은 경우 중단
        
        # 다만 98765 같은 경우 가장 큰 자리수 9에서 올려야 하지만, 9->10을 할 경우 103210이 되어 감소수가 아니게됨.
        # 따라서 이와 같이 n자리수에서 최대케이스의 경우 다음의 감소수는 n(n-1)..210 이 되어야함
        
        if not(n_arr[0] == 9 and j == num_digit-1): 
            n_arr[-1-j] += 1
            
            for k in range(j):
                n_arr[-1-k] = k
                
            new_num = 0
            for l in range(num_digit):
                new_num += n_arr[l] * 10**(num_digit - 1 - l)
        
        else:
            new_num = 0
            for l in range(num_digit):
                new_num += (l+1) * 10**(l+1)
            
        dict_next_dec_num[n] = new_num #결과값을 저장
        return new_num
        
dec_num_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20]

# N번째 감소수를 반환하는 함수
def nth_dec_num(N): 
    #위와 같은 방식으로 시간단축을 위해 결과값을 저장하는 방식
    N_saved = len(dec_num_list)
    if N < N_saved:
        return dec_num_list[N]
    else:
        temp = dec_num_list[-1]
        for iter in range(N-N_saved +1):
            temp = next_dec_num(temp)
            dec_num_list.append(temp)
        return temp

N = int(input())

if N>1022: # N=1022번째 감소수는 9876543210이 되어 이보다 큰 감소수는 존재하지 않음. 따라서 -1 반환
    result = -1
else:
    result = nth_dec_num(N)
    
print(result)

댓글을 작성하려면 로그인해야 합니다.