[BOJ] 1406 에디터

👉 들어가기

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

 문제가 긴 만큼 문제에서 얘기하는 에디터를 만드는 조건을 자세하게 설명해 주었습니다.
조건에 따라 코드를 구현하면 쉽게 풀릴 것이라 생각했지만, 시간초과로 실패하게 되었죠.

 먼저 썼던 방법은, 정수형 인 cursor 를 두고, word 가 담긴 list 하나를 통해 cursor의 위치를 조정하면서 python의 list를 통해 command P 는 insert, command B 는 del 을 이용하여 구현하였기 때문에, 시간복잡도는 O(n)으로 시간을 초과하게 되었습니다.

from sys import stdin
input = stdin.readline

word = list(input().strip())
cursor = len(word)
n = int(input())


for i in range(n):
    cmd = input().split()
    if(cmd[0] == 'L'):
        if(cursor != 0):
            cursor -= 1
    elif(cmd[0] == 'D'):
        if(cursor != len(word)):
            cursor += 1
    elif(cmd[0] == 'B'):
        if(cursor != 0):
            del word[cursor-1]
            cursor -= 1
    elif(cmd[0] == 'P'):
        word.insert(cursor, cmd[1])
        cursor += 1
print("".join(word))

python의 list 의 insert 와 del 은 시간복잡도가 O(n) 입니다.

✏️ 문제 풀이

하지만, 스택과 큐의 push & pop 은 시간복잡도가 O(1) 이다.
따라서 list를 통해 stack 처럼 사용하고자 하였고 해당 문제에서는 커서의 위치를 기준으로 왼쪽 stack을 left로, 오른쪽 stack을 right로 두어 구현하였습니다.

from sys import stdin
input = stdin.readline

word = list(input().strip())
left = []
right = []
n = int(input())

for i in range(len(word)):
    left.append(word[i])

for i in range(n):
    cmd = input().split()
    if(cmd[0] == 'L'):
        if(len(left) != 0):
            tmp = left.pop()
            right.append(tmp)
    elif(cmd[0] == 'D'):
        if(len(right) != 0):
            tmp = right.pop()
            left.append(tmp)
    elif(cmd[0] == 'B'):
        if(len(left) != 0):
            left.pop()
    elif(cmd[0] == 'P'):
        left.append(cmd[1])
right.reverse()
print("".join(left+right))

strip()은 '\n' 을 제거하기 위해 사용하였고,
right.reverse()는 스택의 출력을 위해서 순서를 뒤집었으며
"".join(left+right)을 통해서 left 와 right 를 합치고 하나의 string으로 출력하였습니다!

감사합니다 😁