글 읽기 - 시간초과 부분... 어디부분을 좀더 최적화 할수 있을까요..?

jinyoungcho93 5년 전 0

의미없는 이야기지만.. 3%에서 시간초과 에러가 납니다..

어딜 고쳐야 조금더 괜찮은 코드로 만들수 있을까요??

def d(N):
    if N*2 <= 9999:
        d = N*2
    else: 
        d = N*2 % 10000
    return d

def s(N):
    if N-1 != 0:
        s = N-1
    else:
        s = 9999
    return s

def l(N):
    a = str(N)
    
    if len(a) != 4:
        a = (4-len(a)) * '0' + a
        
    c = 0
    for idx,i in enumerate(a):
        if len(a)-idx == len(a):
            c += int(i)
        else:
            try:
                c += int(i) * 10**(len(a) -idx)
            except:
                print(a)
    return c

def r(N):
    a = str(N)
    
    if len(a) != 4:
        a = (4-len(a)) * '0' + a
    
    c = 0
    for idx,i in enumerate(a):
        if len(a)-idx-1 == 0:
            c += (10**idx) * int(i)
        else:
            c += 10**(len(a)-idx-2) * int(i)
    return c

def get_route(goal):
#     print(goal, c_dic[goal])
    if c_dic[goal][0] == A:
        route.append(c_dic[goal][1])
        return;
    else:
        goal2 = c_dic[goal][0]
        route.append(c_dic[goal][1])
        
        get_route(goal2)
        
        
MAX = 9999
CASE_SIZE = int(input())
from collections import deque,defaultdict

for k in range(CASE_SIZE):

    A,B = map(int,(input().split()))

    check = [False] * (MAX+1)
    c_dic = defaultdict(lambda : -1)
    c_dic[A] = "START"
    q = deque()
    q.append(A)
    check[A] = True
    
    
    while q:
        x = q.popleft()

        dd = d(x)
        ss = s(x)
        ll = l(x)
        rr = r(x)

        if 0<dd and check[dd] == False:
            q.append(dd)
            check[dd] = True
            c_dic[dd] = [x,"D"]


        if 0<ss and check[ss] == False:
            q.append(ss)
            check[ss] = True
            c_dic[ss] = [x,"S"]


        if 0<ll and check[ll] == False:
            q.append(ll)
            check[ll] = True
            c_dic[ll] = [x,"L"]

        if 0<rr and check[rr] == False:
            q.append(rr)
            check[rr] = True
            c_dic[rr] = [x,"R"]
    route = []    
    get_route(B)
    route.reverse()
    
    for z in route:
        print(z, end=' ')

hello70825 5년 전 0

예제조차 정상적으로 출력하지 못하고 있습니다

저도 이 문제 풀 때 엄청 고생했는데 L과 R 변환을 간단하게 만들어야 하더라구요

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

문제

문제

출처

ICPC

시간초과 부분... 어디부분을 좀더 최적화 할수 있을까요..?

jinyoungcho93 5년 전 0

hello70825 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말