https://www.acmicpc.net/problem/9471
시간0.3초, 메모리 512MB
input :
- 문자열 (길이가 N 100,000을 넘지 않는다)
- 명령어의 개수 M(1 ≤ M ≤ 500,000)
output :
- 편집기에 입력되어 있는 문자열을 출력
조건 :
- L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
- D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
- B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임 - P $ $라는 문자를 커서 왼쪽에 추가함
- 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
처음엔 직접 cursor 변수를 만들어서 움직이게 했고.
insert 와 del 메소드를 써서 수행했다.
그러나 리스트안의 메소드의 시간 복잡도가 둘 다 O(N)이기 떄문에 문자열의 길이가 10만에 명령어만 50만 번이 들어온다면 안그래도 시간 제한이 짧기 때문에 당연히 시간 초과가 발생한다.
이를 방지할 방법이 리스트를 2개를 만들어 pop과 append 를 이용하는 것이다.
data의 커서를 왼쪽으로 옮긴다면 data.pop 해서 temp.append 해준다.
반대로 오른쪽으로 옮기면 temp.pop 해서 data.append 해준다.
item 들을 옮겨버리면서 커서가 리스트의 제일 뒤에 존재한다고 생각하는 것이다.
그리고 pop의 경우엔 리스트의 길이가 0보다 커야만 가능 하기 때문에 꼭 조건을 붙여 주어야 한다.
append가 들어가는 경우를 보면
data : abcd
->>
temp : dcba
이렇게 뒤집혀 들어가기 때문에 모든 명령이 끝날 경우
temp를 뒤집어 주어야 한다.
reverse()를 통해 뒤집어 주고 이것을 data와 더해주자.
import sys
data = list(sys.stdin.readline().strip())
temp = []
for i in range(int(sys.stdin.readline())):
cmd = sys.stdin.readline().strip()
if cmd[0] == 'P':
cmd = cmd.split()
data.append(cmd[1])
elif cmd == 'L':
if len(data) > 0:
temp.append(data.pop())
elif cmd == 'D':
if len(temp) > 0:
data.append(temp.pop())
else:
if len(data) > 0:
data.pop()
temp.reverse()
data += temp
print("".join(data))
