DSLR

9019번: DSLR

 

나의 풀이

from collections import deque
import sys

def _cr_dslr(number, now_routing):
    if (now_routing[-1] == 'D'):
        return ((2 * number) % 10000, now_routing)
    elif (now_routing[-1] == 'S'):
        return (9999 if (number == 0) else (number - 1), now_routing)
    elif (now_routing[-1] == 'L'):
        return ((number // 1000) + ((number % 1000) * 10), now_routing)
    elif (now_routing[-1] == 'R'):
        return ((number // 10) + ((number % 10) * 1000), now_routing)

def _dslr(a, b):
    visit = [False]*10000
    queue = deque([(a,'')])
    visit[a] = True

    while True:
        n_num, routing = queue.popleft()
        if (n_num == b):
            return routing

        cr_d, cr_s, cr_l, cr_r = _cr_dslr(n_num, routing + 'D'), _cr_dslr(n_num, routing + 'S'), _cr_dslr(n_num, routing + 'L'), _cr_dslr(n_num, routing + 'R')

        # 방문하지 않았으면 append
        if (visit[cr_d[0]] == False):
            visit[cr_d[0]] = True
            queue.append(cr_d)

        if (visit[cr_s[0]] == False):
            visit[cr_s[0]] = True
            queue.append(cr_s)

        if (visit[cr_l[0]] == False):
            visit[cr_l[0]] = True
            queue.append(cr_l)

        if (visit[cr_r[0]] == False):
            visit[cr_r[0]] = True
            queue.append(cr_r)


n = int(sys.stdin.readline())
for _ in range(n):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    print(_dslr(a, b))

 

시간 복잡도

visit = [False]*10000 : 방문 크기가 10000으로 고정되어 있음
해당 알고리즘 시간복잡도 : 상수시간 ( O(1) )