글 읽기 - [python3] 시간 초과가 나는 부분이 어디인지 감이 안오네요..

vitriol95 3년 전 0

L과 R 커맨드도 문자열을 정수형으로 고쳤고.. 경로도 딕셔너리 형태로 저장해서 왔는데 말이죠.. 어디서 시간 초과가 나는건지 감을 못잡겠습니다. 도와주시면 감사하겠습니다 ㅠ

from collections import deque, defaultdict

def rotate(x, direction):

    x1 = x // 1000  # 1000 자리
    x2 = (x % 1000) // 100  # 100 자리
    x3 = (x % 100) // 10  # 10 자리
    x4 = x % 10

    if direction == 0:
        return x2*1000+x3*100+x4*10+x1
    else:
        return x4*1000+x1*100+x2*10+x3

def bfs(a, b):

    dp[a] = ['l', a]
    q = deque()
    q.append(a)

    while q:

        now = q.popleft()
        temp = [(2 * now) % 10000, now - 1 if now != 0 else 9999,
                rotate(now, 0), rotate(now, 1)]
        for i in range(4):

            if dp[temp[i]]:
                continue

            dp[temp[i]]=[cmd[i],now]
            q.append(temp[i])

            if temp[i] == b:
                return
    return

t = int(input())
cmd = ["D", "S", "L", "R"]

while t:
    a, b = map(int, input().split())
    dp = defaultdict(list)
    bfs(a,b)
    result = []
    while True:
        result.append(dp[b][0])
        if dp[b][1] == a:
            break
        b = dp[b][1]
    print(*result[::-1],sep='')

    t -= 1

suker80 3년 전 1

디폴트 딕셔너리 말고 리스트로 바꿔서 해보세요

딕셔너리 형태가 시간복잡도는 같지만 종종 리스트보다 느릴때가 있습니다

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

문제

문제

출처

ICPC

[python3] 시간 초과가 나는 부분이 어디인지 감이 안오네요..

vitriol95 3년 전 0

suker80 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말