[BOJ] 1406: 에디터

BOJ 1406: 에디터

1406번: 에디터

❓문제 설명

vim, 메모장 에디터를 구현하는 문제이다.

일련의 문자열이 주어지고, 명령어에 따라 커서를 옮기거나, 문자를 추가 혹은 삭제할 수 있다.

명령어 'L' -> 왼쪽으로 커서 옮김

명령어 'D' -> 오른쪽으로 커서 옮김

명령어 'B' -> 커서 왼쪽의 문자 삭제

명령어 'P $' -> 커서 왼쪽에 문자 $ 삽입

 

❗️문제 풀이

"ABCD" 라는 문자열이 주어지면 커서는

"_A_B_C_D_" => 이런 식으로 5개의 자리에 위치할 수 있다.

따라서, 첫 번째 커서의 위치를 주어진 문자열의 길이로 설정했다.

"0 A 1 B 2 C 3 D 4"

 

처음은 시간 복잡도를 고려하지 않고 알고있는 리스트 지식으로 풀었다.

 

import sys
from collections import deque
alpha = list(input())
N = int(input())
cursor = len(alpha)
# print(cursor)
for i in range(N):
    edit = list(sys.stdin.readline().split())
    # print(cursor)
    # print(i,": ", alpha)
    if (edit[0] == "L"):
        if (cursor == 0):
            continue
        else:
            cursor -= 1
    elif (edit[0] == "D"):
        if (cursor == len(alpha)):
            continue
        else:
            cursor += 1
    elif (edit[0] == "B"):
        if (cursor == 0):
            continue
        else:
            del alpha[cursor - 1]
            cursor -= 1
    elif (edit[0] == "P"):
        alpha.insert(cursor, edit[1])
        cursor += 1
print(*alpha, sep="")

각 명령어에 따라 커서의 위치를 옮겼고,

커서 인덱스로 문자를 삭제하거나 추가를 진행했다.

하지만 파이썬의 경우 0.3초의 제한시간이 주어지고,

insert와 del 함수가 최악의 경우 O(n)의 시간복잡도를 갖기 때문에

다른 방법을 찾아야했다.

📌 전체 코드

# BOJ 1406 에디터

import sys
from collections import deque
left = list(input())
right = []
N = int(input())

for i in range(N):
    command = list(sys.stdin.readline().split())
    if command[0] == "L" and left:
        right.append(left.pop())
    elif command[0] == "D" and right:
        left.append(right.pop())
    elif command[0] =="B" and left:
        left.pop()
    elif command[0] == "P":
        left.append(command[1])

if right:
    right.reverse()

print(*(left+right), sep="")

이 경우, 커서를 기준으로 두 개의 스택을 만든다.

각 명령문에 맞게 문자를 커서 기준 왼쪽, 오른쪽 스택으로 옮기거나 문자 삭제 및 추가를 통해 최종 문자열을 만든다.

스택의 FILO 원칙 때문에 커서 기준 오른쪽 스택은 역으로 출력해줘야 한다.