[Coding Test][Python][백준] BOJ #1406 에디터

#1406 에디터

문제)

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

 

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력)

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력)

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

---

풀이)

※ 풀이 아이디어

1. list를 직접 조작할 경우 최악의 경우 : O(NM) = O($ 5 \times 10^10$) 
2. list를 직접 조작하는 것이 아니라 접근을 O(1)으로 해결할 수 있어야한다.
3. 그러면 자료구조를 사용해서 문제를 풀어야한다.
4. Stack의 pop(), push()는 O(1)이므로 이중으로 Stack을 사용한다.

따라서, Cursor를 기준으로 left, right 두 개의 Stack을 관리하면서 연산을 O(1)으로 처리가 가능하게 된다.
이 때 중요한 점은 right를 역순으로 유지해야 한다는 것인데, 이는 append, pop을 사용하기 위함이다.
이를 역순으로 유지하지 않는다면 "L" 연산을 수행할 때 right[0]에 추가해야하는데 이는 right의 원소들을 다 한칸씩 밀어내야하므로 O(N)의 시간복잡도를 가지기 때문이다.

import sys
input = sys.stdin.readline
S = list(input().strip())
M = int(input().strip())

# Stack을 사용한 풀이
# pop, append를 O(1)으로 풀기위한 방법!
# 따라서 Linked List로도 풀 수 있다.

# cursor 기준 왼쪽 오른쪽
left = S
right = []
for i in range(M):
    op = input().strip()
    if op == "L":
        # 커서를 왼쪽으로
        if left:
            right.append(left.pop())
    elif op == "D":
        # 커서를 오른쪽으로
        if right:
            left.append(right.pop())
    elif op == "B":
        # 왼쪽에 있는 문자 삭제
        if left:
            left.pop()
    else:
        op, c = map(str, op.split())
        left.append(c)

res = left + right[::-1]
print(''.join(res))

 

사이트의 예제 입력에 "L" 연산을 추가하여 알고리즘이 동작하는 과정을 쉽게 보기위해 그린 그림입니다.

---

처음에는  문제를 단순하게 접근하여 시간 초과가 났다(시간 제한 0.3초)
0.3초면 어림잡아 $3 \times 10^7$ 이다. 
문자열의 길이가 N($10^5$)이고,  명령어의 수가 M $5 \time 10^5$ 이므로 아래 코드처럼 짰을 때 Worst $5 \ times 10^10$이 나올 수 있다(Operation이 "B"만 나왔을 때)

이 때 위의 풀이처럼 Stack을 사용하면 append와 pop을 O(1)으로 처리할 수 있으므로 O($5 \times 10^5$)으로 해결할 수 있다.  

 

import sys
input = sys.stdin.readline
S = list(input().strip())
M = int(input().strip())

cursor = len(S)
for i in range(M):
    op = input().strip()
    if op == "L":
        if cursor != 0:
            cursor -= 1
    elif op == "D":
        if cursor != len(S):
            cursor +=1
    elif op == "B":
        if cursor != 0:
            S = S[:cursor-1] + S[cursor:]
            cursor -= 1
    else:
        op, c = map(str, op.split())
        S = S[:cursor] + [c] + S[cursor:]
        cursor += 1

print(''.join(map(str, S)))