Baekjoon 9019번 DSLR

문제

https://www.acmicpc.net/problem/9019

걸린 시간

01 : 23 : 19 실패

풀이

PyPy3

from collections import deque
import sys
input = sys.stdin.readline

dslr = ['D', 'S', 'L', 'R']

class DSLR():
    def digit(self, A):
        return '0'*(4-len(str(A)))+str(A)

    def D(self, A):
        result = A*2
        if result > 9999:
            result %= 10000
            return result
        else:
            return result

    def S(self, A):
        result = A-1
        if result < 0:
            return 9999
        else:
            return result

    def L(self, A):
        return (A%1000*10)+(A//1000)

    def R(self, A):
        return (A%10*1000)+(A//10)

def bfs(A):
    q = deque()
    q.append([A, ''])
    visited[A] = True
    cal = DSLR()

    while q:
        v, p = q.popleft()

        if v == B:
            break    

        command = [cal.D(v), cal.S(v), cal.L(v), cal.R(v)]

        for i in range(0, 4):
            if not visited[command[i]]:
                visited[command[i]] = True
                path = p+dslr[i]
                q.append([command[i], path])
    return p

if __name__ == "__main__":
    T = int(input())

    result = []

    for _ in range(0, T):
        A, B = map(int, input().split())
        visited = [False]*10000
        result.append(bfs(A))

    for i in result:
        print(i)

처음 제출했을때 Python3 은 물론이고 PyPy3 로도 시간초과가 나는 문제였다.

백준 질문게시판과 다른 블로거의 풀이에서 원인을 찾을 수 있었다.

1. 정수 보다 문자열을 복사하는데 드는 부담이 더 크다.
2. 메모이제이션에 사용되는 1만 크기의 리스트를 반복문을 사용하여 초기화.

위 두 가지만 고쳐도 통과는 하지만 여기서 L, R 연산을 조금 더 수정하면 실행시간을 절반 정도로 줄일 수 있다.

1. 정수를 4자리 문자열로 바꾸어 deque 에 추가, rotate 메서드 사용 후 join 연산 (이전 풀이)
2. 정수를 4자리 문자열로 바꾸어 인덱싱 (이전 풀이)
3. 몫과 나머지를 이용한 수식연산

PyPy3 로도 겨우겨우 통과하는데 Python3 으로 제출해 더 빠른 속도로 통과한 풀이가 하나 등록되어 있다. 코드가 비공개라 볼 순 없지만 어떻게 작성했는지 알고싶다.

참고

• [백준알고리즘] 9019번: DSLR -Python - 공부노트