문제
요즘 하루에 1문제씩 잘 풀고있다
스스로를 칭찬하며!
요렇게 문자열 위주로 구현하는 문제가 제일 재밌는것 같다
막 이런저런 알고리즘 써야되는건 아는건 쉬운데 안써본건 아예 접근을 못하겠다..
자신있게 풀었는데 시간초과가 떴다
reverse가 시간복잡도가 O(N)이 드니깐 이걸 매번 해주지 말고 나중에 체크해서 한번만 해줘야 겠다 생각했는데
그래도 시간초과가 떠서 고민하다가 새로운걸 공부했다
이 내용은 밑에다가 따로 정리하겠다!
이 문제의 핵심은 reverse를 매번 하지 말고
deque의 popleft는 O(1)인걸 이용해서
reverse 여부를 따로 체크해두면서 그때그때 popleft, pop 을 알맞게 써주는게 아니었을까 싶다.
그 외 부분은 문자열 처리만 하면 된다
내 풀이
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
for _ in range(n):
errCheck = False
order = input()
length = int(input())
arr = input().strip('[]\n')
arr = arr.split(',')
arr = deque(arr)
reverse = False
if length == 0 :
arr = deque()
for i in order:
if i == '\n':
continue
if i == 'R':
reverse = not reverse
elif i == 'D':
# if len(list(arr)) == 0 or list(arr) == ['']:
if len(arr) == 0:
errCheck = True
break
else :
if reverse:
arr.pop()
else :
arr.popleft()
if errCheck:
print('error')
else :
if reverse:
arr.reverse()
print('[' + ','.join(arr) + ']')새로 공부한것
위 코드에서 주석처리한 부분때문에 시간 초과가 났다
list(arr) 의 시간복잡도
굉장히 자주 쓰는 코드 이지만 ,평소 이 부분은 시간복잡도를 별로 신경 안쓰고 사용해 왔다
arr의 길이만큼 시간복잡도가 쓰인다 O(n)
따라서 위 주석부분 처럼 코드를 짜면 매번 list(arr)을 처리하고 비교하게 되므로 o(n)안에 o(n)이 매번 더 돌게 되어 o(n^2)이 되어 시간초과가 났을것이다
그러면 왜 저렇게 짰느냐?!
deque([])
c = '[]'
c = c.strip('[]\n')
했을때 c = '' 가 된다.
이때까지는 len(c) 를 찍으면 0이 나오지만
c = c.split(',') 처리가 되면
c = [''] 가 되고
이때부터는 len(c) 를 찍으면 1이 된다
c = deque(c)로 변환을 해줘도 역시 길이는 1이다
따라서 이렇게 처음부터 [] 빈 배열형태가 주어지면
짜놓은 문자열 처리 결과 deque([''])가 남게되어
len(list) == 0 조건에 걸리지 않아 요상하게 만들었었다.
따라서 미리 길이가 0이면 빈 배열 deque()로 선언을 하던지 아니면
if len(arr) == 0 or arr = deque([''])
로 비교를 해주면 된다.
둘다 통과되지만 역시 if문 안에 deque를 새로 선언하는 형태가 되어서 그런지 매번 선언 연산이 들어가게 되어 후자가 1.5배정도 느리다.
따라서 미리 길이 0인지 체크후에 0이면 빈 deque로 초기화 해주는 전자를 사용했다.
결과
아래것이 전자
위에것이 후자 이다.
1.5배정도 속도차이가 있다
끝!!
