[백준 1406번-파이썬]에디터

백준 (BOJ) 1406번
https://www.acmicpc.net/problem/1406

사용언어 : PYTHON

1.문제

2.풀이

 시간복잡도를 고려해야하는 문제였다.

 처음에는 현재 커서의 위치를 저장하는 cursor변수와, 리스트의 insert, del 메소드를 사용했는데 이렇게 하니 시간초과가 발생했다. 두 메소드의 시간복잡도가 O(n)이고, 이것을 m번 반복하기 때문이었다.

 이 시간초과 문제를 해결하기 위해선 시간복잡도가 O(1)인 pop()과 append()연산을 사용해야 했다. 그리고 cusor변수를 두 개의 리스트를 사용해서 구현할 수 있었다.
 커서를 기준으로 리스트 st와 tmp_st로 나누었다. 커서를 왼쪽으로 옮기면 st에서 pop()하여 tmp_st에 append(), 커서를 오른쪽으로 옮기면 tmp_st에서 pop()하여 st에 append()

모든 연산이 수행 된 이후에는, tmp_st에 문자열들이 거꾸로 저장되어 있으므로, tmp_st를 reversed()한 후 extend하여 st와 합쳐주고, ‘‘.join을 사용하여 문자열로 출력하였다.

3.코드

3-1.시간초과 코드

import sys
input = sys.stdin.readline

st=list(input().rstrip())
cursor=len(st)
m=int(input())

for _ in range(m):
    command=input().split()
    if command[0]=='P':
        st.insert(cursor,command[1])
        cursor+=1
    elif command[0]=='L' and cursor!=0:
        cursor-=1
    elif command[0]=='D' and cursor!=len(st):
        cursor+=1
    elif command[0]=='B' and cursor!=0:
        del st[cursor-1]
        cursor-=1

print(''.join(st))

3-2.정답코드

import sys
input = sys.stdin.readline

st=list(input().rstrip())
m=int(input())

tmp_st=[]

for _ in range(m):
    cmd=input().split()
    if cmd[0]=='L' and len(st)>0:
        tmp_st.append(st.pop())
    elif cmd[0]=='D' and len(tmp_st)>0:
        st.append(tmp_st.pop())
    elif cmd[0]=='B' and len(st)>0:
        st.pop()
    elif cmd[0]=='P':
        st.append(cmd[1])
    
st.extend(reversed(tmp_st))

print(''.join(st))