(Python) - BOJ(1406번) : 에디터

https://www.acmicpc.net/problem/1406

1406번: 에디터

---

• 문제 : 

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

 

 초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

 

 

 

---

• 풀이 :

문자열의 최대 길이가 100,000이고 명령어가 최대 500,000회 실행되므로 O(n)의 실행시간이 걸리는 del이나 remove를 사용한다면 무조건 시간초과가 나오게 된다. 심지어 시간제한도 0.3초로 다른문제보다 짧다.

 

이를 해결하기 위해 양방향으로 삽입과 삭제가 가능한 deque라는 자료구조를 사용하였다. deque에 대한 개념은

여기를 확인하면 된다.

 

아이디어는 매 커서의 움직임마다 커서의 인덱스를 변화시키는것이 아닌 deque을 변화시키는 방법으로 해결했다.

cursor가 맨 앞일 때 삭제와 왼쪽 이동, 맨 뒤일 때 오른쪽 이동에 대한 예외처리를 해주기 위해 cursor와 l이라는 변수값을 사용하였다. 

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
input = sys.stdin.readline
S = deque(input().strip())
l = len(S)
cursor = l
for _ in range(int(input())):
    C = input().strip()
    if C == 'L':
        if cursor != 0:
            S.appendleft(S.pop())
            cursor -= 1
    elif C == 'D':
        if cursor != l:
            S.append(S.popleft())
            cursor += 1
    elif C == "B":
        if cursor != 0:
            S.pop()
            cursor -= 1
            l -= 1
    else:
        S.append(C[-1])
        cursor += 1
        l += 1
for _ in range(cursor):
    S.appendleft(S.pop())
print("".join(S))