알고리즘 - Python / 백준 - 1406번 : 에디터

1406번: 에디터 (acmicpc.net)

1406번: 에디터

 

---

풀이

• 리눅스 vi 에디터 같은 형태의 에디터를 직접 구현하는 문제다.
• 문제만 읽었을 때는 어려운 부분이 없어 보이지만 , 시간제한을 0.3초 밖에 주지 않는 문제다.
• 문자열의 원하는 위치에 삽입 혹은 삭제가 가장 시간을 많이 잡아먹는 작업일 테고 이를 효과적으로 줄이는 것이 중요할 것이다.
• 커서의 위치와 문자열 시작 위치를 저장해놓고 , 커서를 좌우로 옮길 때 , deque를 rotate 해주는 방식으로 구현하였다.
• 만약 커서를 좌로 한칸 옮긴다면 , 문자열 배열이 우로 한 칸 움직이는 것과 같기 때문이다.
• deque의 rotate 시간 복잡도는 옮기는 칸에 비례하는 선형 복잡도이다.
• 어차피 1칸씩 밖에 안 움직이니 별 문제없다.
• 커서를 움직일 때 , 가장 오른쪽이나 왼쪽인 경우 움직이지 않도록 처리해야 하므로 커서의 위치를 기억하고 , 문자열을 출력할 때 가장 처음의 위치도 기억하고 있어야 하니 이 부분도 기억하고 있다가 나중에 정답을 출력할 때 활용한다.

 

import sys
from collections import deque
s = deque(sys.stdin.readline().strip())
n = int(sys.stdin.readline())
cs = len(s)
start = 0
for _ in range(n):
    inp = sys.stdin.readline().strip()
    if inp == "L":
        if cs != 0:
            cs -= 1
            s.rotate(1)
            start += 1
    elif inp == "D":
        if cs != len(s):
            cs += 1
            s.rotate(-1)
            start -= 1
    elif inp == "B":
        if cs != 0:
            if len(s) != 0:
                s.pop()
                cs -= 1
    else:
        o,t = inp.split(" ")
        s.append(t)
        cs += 1

ans = ''.join(i for i in s)
print(ans[start:len(s)] + ans[0:start])

---