[Python/백준] #1406- [에디터] [try_again]

[에디터]-1406번

1406번: 에디터

My answer-시간초과

import sys
word,n=input(),int(input())
loc=len(word)

for i in range(n):
    tmp=sys.stdin.readline().rstrip().split()
    if(tmp[0]=='L'):
        if(loc!=0):loc-=1
    elif(tmp[0]=='D'):
        if(loc!=len(word)):loc+=1
    elif(tmp[0]=='B'):
        if(loc!=0):
            word=word[:loc-1]+word[loc:]
            loc-=1
    else:
        word=word[:loc]+tmp[1]+word[loc:]
        loc+=1
print(word)

 

Another answer

import sys
 
tmp1 = list(sys.stdin.readline().strip())
tmp2 = []
n = int(input())
for order in sys.stdin.readline.split():
    if order[0] == 'L':
        if tmp1: 
        	tmp2.append(tmp1.pop())
        else: 	
        	continue
    elif order[0] == 'D':
        if tmp2: 
        	tmp1.append(tmp2.pop())
        else: 
        	continue
    elif order[0] == 'B':
        if tmp1: 
        	tmp1.pop()
        else: 
        	continue
    elif order[0] == 'P':
        tmp1.append(order[2])
print(''.join(tmp1 + list(reversed(tmp2))))

우선 맨처음에 문제 자체는 그냥 간단했다. 그래서 풀었는데 시간초과가 떴다..이래서 알고리즘을 공부해야하는구나를 느끼고 있다. 우선 나는 그냥 문자열에서 커서를 정수인덱스로 설정해서 옮기면서 삭제하고 붙였는데, 슬라이싱해서 삽입,삭제하는 거는 시간복잡도가 o(n) 걸리는데, 문제조건에서 반복횟수가 늘어날수록 수가 기하급수적으로 커져서 시간초과가 났다. 그래서 찾아보니 시간복잡도를 줄이기 위해서는 리스트의 마지막에서만 삭제,추가가 되도록 짜던지 아니면 중간의 원소를 삭제 삽입할 때 다른 원소들의 순서는 건들이지 않는 방법을 찾아야 시간복잡도가 o(1)이 걸려서 통과할 것 같았다. 아래 두번째 코드는 스택을 두개를 만들어서 푼 문제이다. 커서를 움직이는 방향을 따라서 스택에서 pop에서 옮겨주면되는 것이다. 예를 들어 커서를 왼쪽으로 움직이려면 첫번째 스택에서 top원소를 pop해서 두번째 스택에 옮기고, 반대로 오른쪽으로 옮길 때는 두번째 스택에서 팝해서 첫번째로 옮기면 된다. 이렇게 문제를 풀면 시간초과가 안나고 통과했다. 코드는 그저그런 컴공생님의 블로그를 보고 해결했다.