[Python] 1406번 : 에디터

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

1406번: 에디터

 

문제 3줄 요약

1. 편집기에 위와 같은 4가지 기능이 있다.

2. 초기 문자열에서 입력한 명령어를 차례대로 실행한다.

3. 남은 문자열을 출력해라!

 

---

 

L은 커서를 왼쪽으로 한 칸,

R은 커서를 오른쪽으로 한 칸,

B는 커서 왼쪽 문자 삭제,

P $는 $라는 문자를 커서 왼쪽에 추가.

 

(여기서 커서는 문자열 오른쪽 끝에서 시작!!)

 

쉽게 말해,

왼쪽 이동, 오른쪽 이동, 문자 삭제, 문자 추가가 되겠다.

 

문제만 딱 봤을 때,

굉장히 쉽게 구현할 수 있다고 생각했고

어렵지 않았다!

 

바로 제출.

 

---

 

문자 삭제 또는 문자 추가 기능에서

커서 왼쪽이 문자열의 중간 부분이라면,

리스트의 insert 함수와 같이 중간에 값을 끼워 넣거나,

remove 함수로 지워야할텐데

 

그럼 시간 초과가 뜬다.

때문에 insert 함수를 쓰지 않고 끼워 넣고, remove 함수를 쓰지 않고 지워야 한다.

 

그말인 즉,

append 함수만 이용하여, 값을 넣고

pop 함수만 이용해서 값을 지우면 된다.

 

커서를 기준으로 왼쪽에 있는 문자는 L_list,

커서 기준 오른쪽에 있는 문자는 R_list로 나누어 주어

추가, 삭제를 해주면

코드를 몇 줄만 바꿔도 시간 복잡도가 매우 줄어든다.

 

하지만 R_list 에서는

값을 왼쪽으로도 넣어야하기 때문에,

덱을 사용하여 구현하였다.

 

 

from sys import stdin
from collections import deque

if __name__ == "__main__":
    L_list = deque(stdin.readline().strip())
    R_list = deque()
    N = int(stdin.readline())

    cursor = len(L_list)
    for _ in range(N):
        command = list(stdin.readline().split())
        # P : 커서 왼쪽에 문자 추가
        if len(command) > 1:
            L_list.append(command[1])
            cursor += 1
        # L : 커서 왼쪽으로 이동
        if command[0] == "L" and cursor > 0:
            R_list.appendleft(L_list.pop())
            cursor -= 1
        # R : 커서 오른쪽으로 이동
        if command[0] == "D" and cursor < len(R_list)+len(L_list):
            L_list.append(R_list.popleft())
            cursor += 1
            
       	# B : 커서 왼쪽 문자 삭제
        if command[0] == 'B' and cursor > 0:
            L_list.pop()
            cursor -= 1

    print(''.join(L_list+R_list))

 

커서가 왼쪽으로 이동한다면,

당연하게 커서 기준 오른쪽 자료구조인 R_list로 값을 첫 번째 인덱스에 넣어준다.

오른쪽 이동 또한 반대로 해주면 된다.

 

제출하면,

 

끝!