[c++] 백준 에디터(1406), 연결리스트

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

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

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

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

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

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

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

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

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

 

풀이

stl list는 양방향 연결 리스트의 구조를 가지고 있으며, 간단히 함수를 호출하여 리스트에 추가,제거,변경 등이 용이하다.

 

커서의 이동이 중요하다. 

 

연결리스트에서 커서가 가르키는 곳이 다음 구조체의 주소라고 생각하면 됨.

 

커서는 초기에 문자열의 맨 왼쪽에 있으므로, 문자열의 크기만큼 커서의 값을 지정한 후, 'L'과 같은 명령어를 받으면 커서의 값을 줄임. 

 

커서가 가르키는 곳이 곳 리스트의 특정 인덱스의 값이 된다. 

# STL <list> 정리

https://forward-gradually.tistory.com/13

c++ STL <list> 정리

 

코드

 

알게 된 점

연결리스트의 매커니즘에 대해서 공부하게 되었음.

 

추후에 low-level의 여러가지 연결 리스트를 구현해봐야겠다.

 

Git-Hub 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/4.%20%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8/%EC%97%90%EB%94%94%ED%84%B0.cpp