글 읽기 - 어떤 부분에서 시간초과가 나는 걸까요?

(追記) (追記ここまで)

어떤 부분에서 시간초과가 나는 걸까요?

9019번 - DSLR

egnever4434 1년 전 0

그나마 생각나는건 41번 라인 문자열 복사, .append()를 자주 쓴 것 정도 말고는 없는데 뭐가 문제인 걸까요?

import sys
from collections import deque
input = sys.stdin.readline
INF = 10000
def operate(old : int, route : str):
 if route == 'D':
 return ((old * 2) % INF, 'D')
 elif route == 'S':
 return ((old - 1) if old > 0 else INF - 1, 'S')
 elif route == 'L':
 return ((old%1000 * 10) + old//1000, 'L')
 else:
 return ((old%10 * 1000) + old//10, 'R')
def get_route(old : int, new : int):
 dslr = ['D', 'S', 'L', 'R']
 visited = []
 num_q = deque()
 route_q = deque()
 num_q.append(old)
 route_q.append("")
 answer = ""
 while True:
 current = [num_q.popleft(), route_q.popleft()]
 if current[0] not in visited:
 visited.append(current[0])
 if current[0] == new:
 answer = current[1]
 break
 for i in range(4)
 tmp = operate(current[0], dslr[i])
 if tmp[0] not in visited:
 num_q.append(tmp[0])
 route_q.append(tmp[1] + current[1])
 return answer
tc = int(input())
for _ in range(tc):
 before, after = map(int, input().split())
 print(get_route(before, after)[::-1])

siyamaki 1년 전 2

시간초과의 원인

1. visited같은 list자료구조의 조건문에서 not in/in 은 O(N)입니다.

2. 파이썬 문자열은 + 연산 시 새로운 문자열을 계속해서 만들어내기 때문에 시간/메모리적 효율이 매우 좋지 않습니다.

3. 그럼 지나왔던 방법은 어떻게 추적하는지?

지나왔던 경로에서 이전 경로를 저장하는 track 배열 하나를 만들고 track[next] = prev형식으로 저장해놓은 다음 도착지 > 출발지로 역 추적하는 방법이 있습니다.

egnever4434 1년 전 0

덕분에 탈출했습니다.. 감사합니다

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

어떤 부분에서 시간초과가 나는 걸까요?

egnever4434 1년 전 0

siyamaki 1년 전 2

egnever4434 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말