텍스트 편집기

시간 제한2초메모리 제한256 MB

요약

커서가 있는 텍스트 편집기를 구현하여 이동, 삽입, 삭제, 읽기 연산을 처리하고 Get 연산마다 커서 뒤의 문자열을 출력합니다.

난이도: 보통10점 중 6점
유형: 구현, 연결 리스트, 문자열
정답자: 아직 제출이 없습니다

문제

아주 먼 옛날, DOS 3.x 시절의 프로그래머들은 EDLIN에 싫증을 내기 시작했고, 점차 직접 만든 편집기로 바꿔 갔다.

수년 뒤 Alex는 그 시절의 텍스트 편집기를 우연히 발견했다. 기본 테스트를 해 본 결과, 이 프로그램은 초당 수만 번의 편집 연산을 수행할 수 있었다(물론 이런 테스트는 손으로 할 수 없다). 지금 Alex는 이런 제품을 직접 만들어 보려고 잠 못 이루는 밤을 보내고 있다. 그를 도와줄 수 있겠는가?

'텍스트 편집기'라는 말을 구체적으로 정하기 위해 Alex는 다음과 같이 정의했다.

텍스트: ASCII 문자 중 값이 $[32, 126]$ 범위에 있는 문자로 이루어진 0개 이상의 문자열이다. 공백과 출력 가능한 문자를 모두 포함한다.
커서: 텍스트 안의 위치를 나타내는 표시다. 텍스트의 맨 앞, 맨 끝, 또는 인접한 두 문자 사이 어디에든 놓일 수 있다.
텍스트 편집기: 텍스트 블록과 커서 하나를 담고 있으며, 아래의 여섯 가지 연산을 수행할 수 있는 프로그램이다. 텍스트 블록이 비어 있으면 텍스트 편집기도 비어 있다고 본다.

연산	입력 형식	기능
Move(k)	`Move k`	커서를 텍스트의 $k$ 번째 문자 바로 뒤로 옮긴다. $k = 0$ 이면 커서를 텍스트의 맨 앞으로 옮긴다.
Insert(n, s)	`Insert n↵ s`	커서 위치에 길이가 $n$ ( $n \geq 1$ )인 문자열 $s$ 를 삽입한다. 커서 위치는 바뀌지 않는다.
Delete(n)	`Delete n`	커서 뒤에 있는 $n$ ( $n \geq 1$ )개의 문자를 삭제한다. 커서 위치는 바뀌지 않는다.
Get(n)	`Get n`	커서 뒤에 있는 $n$ ( $n \geq 1$ )개의 문자를 출력한다. 커서 위치는 바뀌지 않는다.
Prev	`Prev`	커서를 문자 하나만큼 뒤로 옮긴다.
Next	`Next`	커서를 문자 하나만큼 앞으로 옮긴다.

예를 들어, 빈 편집기에 Insert(13, "Balanced tree"), Move(2), Delete(5), Next(), Insert(7, "editor"), Move(0), Get(16) 연산을 차례로 주면 "Bad editor tree"가 출력된다.

과제는 다음과 같다.

빈 텍스트 편집기를 만든다.
입력에서 연산을 읽어 실행한다.
Get() 연산마다 올바른 내용을 출력한다.

제한:

Move() 연산은 50000번을 넘지 않는다. Insert()와 Delete() 연산의 합은 4000번을 넘지 않는다. Prev()와 Next() 연산의 합은 200000번을 넘지 않는다.
한 번의 Insert()에서 삽입되는 문자는 2M개를 넘지 않는다(1M = 1024×1024). 올바른 출력의 길이는 3M을 넘지 않는다.
각 Delete()와 Get() 연산에서 커서 뒤에는 항상 충분한 문자가 있다. Move(), Prev(), Next()는 커서를 잘못된 위치로 옮기지 않는다. 모든 연산은 유효하다.

입력

첫 줄에 연산의 개수 $t$ 가 주어진다. 이어지는 $t$ 줄에 연산이 주어진다.

Insert() 연산 뒤의 문자열에는 줄바꿈이 여러 번 들어 있을 수 있다. 이 줄바꿈은 무시한다. 줄바꿈을 제외하면 입력의 모든 문자는 ASCII 값이 $[32, 126]$ 범위에 있다. 줄 끝에는 공백이 없다.

출력

각 Get() 연산에 대해 요청된 텍스트를 한 줄에 하나씩 출력한다.

예제1

예제 1

입력

15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 16
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22

예상 출력

.\/.
abcde^_^f.\/.ghijklmno