글 읽기 - 1987 알파벳 파이썬 시간

purpose 3년 전 0

안녕하세요.

visitedAlpha로 방문한 알파벳을 저장하였습니다.

3가지 방법으로 해보았는데 1, 2번은 시간초과가 발생하였고, 3번에서 통과를 하였습니다.

1) visitedAlpha = [] # 리스트로 구현, 17번 행 pop()이용 -> 시간초과

2) visitedAlpha.deque() # from collections import deque 후 deque로 구현, 17번 행 pop()이용 -> 시간초과

3) visited = "" # 문자열로 구현, 17번 행 visitedAlpha = visitedAlpha[:-1]이용 -> 통과

제출 번호는 각각 26425302, 26425745, 26425827입니다.

세 방식의 시간복잡도가 어떤 부분에서 달라질 수 있는지 알려주실 수 있을까요??

감사합니다!

import sys
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def backtrack(x, y, visitedAlpha, cnt):
    global ans
    if cnt > ans:
        ans = cnt
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in visitedAlpha:
                visitedAlpha += board[nx][ny]
                backtrack(nx, ny, visitedAlpha, cnt+1)
                visitedAlpha = visitedAlpha[:-1]
                
# [행][열]
R, C = map(int, input().rstrip().split())
board = [] # [0~R-1][0~C-1]
for i in range(R):
    string = input().rstrip()
    board.append(list(string))

# 좌측 상단 처리
visitedAlpha = ""
visitedAlpha += board[0][0]
ans = 1

backtrack(0, 0, visitedAlpha, 1)

print(ans)
    