[백준] 알고리즘 1406번 - python 풀이

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

1406번: 에디터

문제

---

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

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

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

L  커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)

D  커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)

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

P $  $라는 문자를 커서 왼쪽에 추가함

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

---

처음 접근 방식은 cursor라는 변수로 문자열에서 커서의 인덱스 위치를 저장하게 해 문자열을 인덱스로 슬라이싱 하면서 추가 및 삭제하는 방법이다.

from sys import stdin

st = stdin.readline().strip()
n = int(input())
cursor = len(st)
for line in stdin:
    if line[0] == 'L':
        if not cursor == 0:
            cursor -= 1
        else: continue
    elif line[0] == 'D':
        if not cursor == len(st):
            cursor += 1
        else: continue
    elif line[0] == 'B':
        if not cursor == 0:
            st = st[0:cursor-1] + st[cursor:]
        else: continue
    elif line[0] == 'P':
        st = st[0:cursor-1] + line[2] + st[cursor:]
print(st)

당연히 입력 받는 함수는 sys.stdin을 사용했다.

list를 사용하지 않고 문자열로 직접 자른 이유는 list로 슬라이싱 하거나 insert() 메소드를 사용하는 것 보다 직접 슬라이싱하고 합치는 방법이 더 빠르기 때문이다.

이를 눈으로 확인해 봤던 간단한 테스트 코드

import time

li = [1,2,3,4,5,6,7,8,9,0] * 60000
st = '1234567890' * 60000

start = time.time()
st = st[:1000] + '1' + st[1000:]
print(time.time() - start)

start = time.time()
li = li[:1000] + [1] + li[1000:]
print(time.time() - start)

start = time.time()
li.insert(1000, 1)
print(time.time() - start)

result

list를 자른는 것 보다 약 5배, insert()보다 약 2배 정도 빠른 성능을 보인다.

하지만 시간 초과가 난다.

이를 해결하는 것이 이 문제의 핵심이라 생각했다.

문제를 자세히 보면 다른 문제보다 제한 시간이 박한 것을 알 수 있다.

파이썬이 가뜩이나 느린데다가 포인터를 사용할 수 없기 때문에(최소한 내가 지금 알고 있는 지식으로는) 조금이라도 줄일 수 있는 별 방법을 다 시도해 보면서 많은 실패를 하다가 시간을 줄여야 할 핵심 부분이 어디인지 문제를 다시 봤다.

 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다.

문자열의 최대 길이가 100,000인데, 명령어의 최대 개수는 500,000으로 오히려 더 많다. 따라서 최악의 경우 문자를 삭제했다 지웠다를 반복하면, 약 100,000번의 연산을 500,000할 수도 있겠다는 생각을 하니까 어쩔 수 없는 500,000번의 반복을 보다 빠르게 하는 것이 아닌 100,000번의 연산 횟수 자체를 줄여야 한다는 생각을 했다.

지금 작성한 코드로는 삭제나 추가 연산이 모두 O(n)의 시간복잡도가 소요된다. 이를 O(logn)이나 O(1)로 줄여야 하는데, 떠오르는 방법은 linked list나 stack의 사용이었다. 사실 linked list가 가장 먼저 떠올랐는데 파이썬이기 떄문에 접었고... stack을 생각해 보니까 바보같이 매번 문자열을 자르면서 삭제나 추가할 필요가 없음을 느꼈다.

방법은 두 개의 스택을 이용해 편집기의 문자열을 땠다 붙였다 하는 방법이다. 이 두 개의 스택은 다음과 같이 문자열을 잘라서 가지게 될 것이다.

스택 그림

먼저 첫 번째 스택에 입력된 첫 문자열을 모두 담는다.

이때 커서 역할을 하는 것이 첫 번째 스택의 top이다.

커서를 왼쪽으로 움직이면 첫 번째 스택의 top을 pop한 뒤 이 결과를 두 번째 스택에 push하면 자연스럽게 커서가 왼쪽으로 움직인 효과를 낼 수 있다.

반대로 커서를 오른쪽으로 움직이면 다시 두 번째 스택의 top을 첫 번째 스택에 push 해주면 된다.

따라서 첫 번째 스택이 빈다면 커서가 문자열의 맨 왼쪽에 위치한 것이고, 두 번쨰 스택이 빈다면 커서가 문자열의 맨 오른쪽에 위치한 것이다.

문자를 추가하는 'P' 연산 역시 첫 번째 스택에 추가할 문자를 push해 주면 된다.

from sys import stdin

stk1 = list(stdin.readline().strip())
stk2 = []
n = int(input())
for line in stdin:
    if line[0] == 'L':
        if stk1: stk2.append(stk1.pop())
        else: continue
    elif line[0] == 'D':
        if stk2: stk1.append(stk2.pop())
        else: continue
    elif line[0] == 'B':
        if stk1: stk1.pop()
        else: continue
    elif line[0] == 'P':
        stk1.append(line[2])
print(''.join(stk1 + list(reversed(stk2))))

이 방법으로 작성할 때도 collections의 deque를 사용할까 했는데, 어차피 list의 pop() 연산과 append() 연산도 O(1)이라 사용하지 않았다. (파이썬 함수의 시간복잡도는 아래 글을 참조했는데 좋은 정리 글 감사합니다)

https://wayhome25.github.io/python/2017/06/14/time-complexity/

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

결과