[BOJ]1406 - 에디터 (Python)

문제 

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

코드 #1 - WRONG ❌

from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()

str = deque(input())
n = int(input())
cursor = len(str)
for _ in range(n):
    op = input().split()
    if op[0] == 'L' and cursor != 0:
        cursor -= 1

    elif op[0] == 'D' and cursor != len(str):
        cursor += 1

    elif op[0] == 'B' and cursor != 0:
        del str[cursor - 1]
        cursor -= 1

    elif op[0] == 'P':
        str.insert(cursor, op[1])
        cursor += 1

print(''.join(str))

 

풀이 #1 - WRONG ❌

처음에 풀었을 때는 시간 복잡도를 생각하지 않고 풀었다

입력 수가 좀 많다고 생각은 했지만 그냥 아무생각 없이 풀었던 것 같다 

당연히 시간 초과가 나왔고 질문 글을 찾아보니까 2가지의 해결 방법이 있었다. 

• list의 맨 뒤에서만 삭제/삽입 할 수 있게 알고리즘 짜기 
• 가운데에서 값을 넣고 빼도 양쪽 값 말고는 영향을 받지 않는 자료구조 사용하기 

2번을 충족시키기 위해서는 linked list를 사용해야 하는데 그렇게 하는 것보다는 1번 방법으로 하는 것이 더 효율적일 것이라고 판단하여 다시 풀어보았다 

list 관련 함수의 시간복잡도를 찾아보니 append()와 pop()은 O(1)이고 내가 사용한 del과 insert()는 O(N)의 시간복잡도를 갖고 있었다

 

코드

import sys
input = lambda : sys.stdin.readline().strip()

str = list(input())
s = []
n = int(input())
cursor = len(str)

for _ in range(n):
    op = input().split()
    if op[0] == 'L' and len(str) != 0:
        s.append(str.pop())
    elif op[0] == 'D' and len(s) != 0:
        str.append(s.pop())
    elif op[0] == 'B' and len(str) != 0:
        str.pop()
    elif op[0] == 'P':
        str.append(op[1])

print(''.join(str + list(reversed(s))))

풀이

2개의 리스트를 사용해서 풀었다 

str[]은 처음에 받는 문자를 저장하는 리스트이고, s[]는 커서를 이동시키고 원소를 추가할 때 필요한 리스트이다

커서는 항상 str의 마지막에 있다고 생각한다

 

"L"인 경우, 커서가 왼쪽으로 움직여야 하니까 str에 있는 가장 마지막 값을 s에 옮긴다 

"D"인 경우, 커서가 오른쪽으로 움직여야 하니까 s에 있는 마지막 값을 다시 str으로 옮긴다 

"B"의 경우, 커서의 왼쪽 값을 지우는 것이므로 str의 마지막 원소를 지운다 

"P"의 경우, 커서의 왼쪽에 값을 추가하는 것이므로 str의 맨 뒤에 값을 추가한다 

 

마지막으로 출력할 때 2번째 리스트를 거꾸로 원래 리스트에 붙여준다 

2번째 리스트의 맨 마지막이 커서의 오른쪽 값이라고 보고 문제를 풀었기 때문이다