문제 설명
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
| 명령어 | 내용 |
|---|---|
| L | 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) |
| D | 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) |
| B | 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) |
| P $ | $라는 문자를 커서 왼쪽에 추가함 |
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
풀이
문자열로 풀면 시간 복잡도가 O(n²)이지만 스택으로 풀면 O(n)으로 풀 수 있다.
괄호를 기준으로 스택을 두 개 만들어서 풀면 쉽다.
괄호를 가운데 두고 left와 right라는 두 스택이 있다고 치자.
커서가 문장 맨 뒤에 위치한 경우는 left에만 글자가 들어있고 right는 비어있는 상태일 것이다. 반대로 커서가 문장 맨 앞에 위치한 경우는 left 스택이 비어있을 것이다.
L연산을 수행하면 커서를 왼쪽으로 한 칸 옮기는 것이기 때문에 left 맨 위의 값을 지우고 right로 옮기면 된다.
D연산은 오른쪽으로 한 칸 옮기는 거니까 right 맨 위의 값을 left로 옮기는 것과 똑같다.
B연산은 커서 왼쪽의 문자를 삭제하는 것이므로 left 맨 위의 값을 지우면 된다.
P연산은 $라는 문자를 커서 왼쪽에 추가하는 것이므로 left에 $를 push해주면 된다.
각각 문장의 맨 뒤거나 맨 앞일 때 무시된다는 조건도 추가해서 코드를 짜면 다음과 같다.
- 처음에 input()으로 풀었다가 시간초과로 실패했는데
그냥 이젠 sys.stdin.readline() 쓰는 걸 습관화해야할 듯
제출 코드
import sys
basic = sys.stdin.readline().rstrip()
m = int(sys.stdin.readline())
left = list(basic)
right = []
for i in range(m):
co = sys.stdin.readline().split()
if co[0] == "L":
if not left:
pass
else:
right.append(left[-1])
left.pop()
elif co[0] == "D":
if not right:
pass
else:
left.append(right[-1])
right.pop()
elif co[0] == "B":
if not left:
pass
else:
left.pop()
elif co[0] == "P":
left.append(co[1])
arr = left + right[::-1]
print(''.join(arr))