문제
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
L- 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D- 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B- 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P$- $라는 문자를 커서 왼쪽에 추가함
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
입력
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.
출력
첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.
풀이
풀이 1
연결리스트를 활용하는 문제이다. c++에서 연결리스트는 list로 구현되어있다.
List의 기본 사용법
- 기본 선언 : list<[datatype]> 변수이름;
- list.front(): 맨 앞의 원소를 참조 및 반환
- list.back(): 맨 뒤의 원소를 참조 및 반환
- list.begin():맨 앞의 원소를 가리키는 iterator를 반환
- list.end(): 맨 마지막의 다음 원소를 가리키는 iterator 반환
- list.rbegin(): 뒤에서부터 순차적으로 접근할 때 사용, 뒤집었을 때 첫번째 원소 반환
- list.rend(): 뒤에서부터 순차적으로 접근할 때 사용, 뒤집었을 때 마지막 원소 반환
- list.push_back(): 맨 뒤에 원소 삽입
- list.push_front(): 맨 앞에 원소 삽입
- list.pop_back(): 맨 마지막 원소 pop
- list.pop_front(): 맨 처음 원소 pop
- list.insert(iter, k): iter가 가리키는 위치에 원소 k삽입, 삽입한 원소를 가리키는 iterator 반환
- list.erase(iter): iter가 가리키는 원소 삭제, 삭제한 다음 원소를 가리키는 iterator반환
- list.size(): 원소의 개수 반환
- list.remove(k): k와 같은 원소 모두 제거
- list.remove_if(predicate): 단항 조건가 predicate에 해당하는 원소 모두 제거
- li.reverse(): 원소들의 순차열을 뒤집음
- li.sort(): 모든 원소를 오름차순(default)으로 정렬, 파라미터로 정렬 기준 받아서 그 기준으로 정렬 (linked list setSortRule이랑 똑같음)
이 정도로 정리해보겠다.
원래 200,000 크기의 배열 공간을 두는 것을 생각해봤는데, 그러면 커서가 같은 위치에서 여러개를 입력하게 되는 것이 불가능해지므로 연결리스트를 사용하게 됐다.
벡터로도 가능한가..?
리스트와 벡터의 차이 > https://velog.io/@soohyeonb_9/list%EC%99%80-vector-%EC%B0%A8%EC%9D%B4%EC%A0%90
#include <iostream>
#include <list>
using namespace std;
int main()
{
//1. 문자열 입력받기
list<char> ls;
string init;
cin >> init;
for(auto c: init) ls.push_back(c);
//2. 커서 맨 뒤에 두기
auto cursor = ls.end();
//3. 명령어 개수 입력받기
int commandNum;
cin >> commandNum;
//4. 입력된 명령어 수행
while(commandNum--){
char op;
cin >> op;
if(op == 'L'){
if(cursor != ls.begin())
cursor--;
}
else if(op == 'D'){
if(cursor != ls.end())
cursor++;
}
else if(op == 'B'){
if(cursor != ls.begin()){
cursor--;
cursor = ls.erase(cursor);
}
}
else{ //'P'
char newChar;
cin >> newChar;
ls.insert(cursor, newChar);
}
}
for(auto c:ls){
cout << c;
}
return 0;
}List의 erase 함수에 대한 고찰
문제를 풀면서
cursor--;
cursor = ls.erase(cursor);
}erase() 함수에 대한 이해가 필요했다.
커서를 하나 줄이고 커서가 가리키는 부분을 지운 다음 커서에 새로운 커서를 넣어줘야 한다.
왜일까?
erase()함수는 iterator를 인자로 받는데, 여기서 iterator는 한마디로 포인터이다. 즉, 배열의 요소를 가리키는 iterator를 인자로 받아서 iterator가 가리키는 배열의 요소를 삭제한다. 그러면 iterator는 가리키던 요소가 사라졌기 때문에 쓰레기값이 들어가게 된다.
erase() 함수는 반환 값으로 삭제된 요소의 다음 요소를 가리키는 iterator를 반환한다. 따라서 반환된 값을 cursot에 다시 넣어줘야 우리가 원하는 커서의 역할을 수행할 수 있는 것이다.
또한 list.end()와 list.begin()은 가리키는 것이 조금 다르다.
- begin(): 첫번째 요소를 가리키는 반복자 반환
- end(): 마지막 요소 바로 뒤의 요소를 가리키는 반복자 반환
list와 vector의 차이
물론 리스트는 연결리스트를 구현한 것이고 벡터는 동적 배열을 구현한 자료구조이지만, insert와 erase를 할 때 조금 차이가 있다.
우선 vector는 해당 원소가 삭제되면 iterator의 공백을 삭제된 원소 다음에 있는 원소 위치로 채워지게 된다. 배열에서 삭제된 요소 뒤의 요소들이 모두 앞으로 자동으로 밀리게되는 것이다. 하지만 list는 vector와는 달리 BidirectinalIterator이기 때문에 순서대로 차근차근 접근이 가능하다. 이 때문에 특정한 원소가 삭제되면 해당 원소를 가리키고 있던 iterator가 그 다음 위치를 잃어버리게 되는 것이다.
erase 사용 예시
- erase()함수 리턴값 사용하기
for( Iterator = List.begin(); Iterator != List.end(); )
{
Iterator = List.erase(Iterator); //이렇게 erase()가 리턴하는 iterator 값을 저장해서 포인터를 갱신해서 사용하는 방법이 있다.
}- 후위 연산 ++ 쓰기
for( Iterator = List.begin(); Iterator != List.end(); )
{
List.erase(Iterator++);
}1 2 3이 있다고 할 때 Iterator가 만약 2를 가리키고 있으면 후연산 ++을 사용하여 2원소를 erase()로 삭제하고, Iterator는 ++된 값인 3을 가리키게끔 하는 방법이다. a++ 과 ++a의 차이는 알았지만..(알았다고 할 수 있을...까...?) ++연산이 되는 정확한 타이밍을 몰랐어서 이해하는데 한참 걸렸다.......
Iterator ++가 되면 우선 erase()안에는 2가 들어가게 되는 거고 Iterator는 유유자적하게 3을 가리키고 있는 것이다.
- 잘못된 사용 사례
for( Iterator = List.begin(); Iterator != List.end(); Iterator++)
{
List.erase(Iterator);
}이렇게 Iterator ++위치가 바뀌게 되면 erase()연산을 할 때 iterator가 그냥 사라지게 되어 쓰레기 값이 저장되게 된다. 그 상태에서 iterator++ 연산이 수행되므로 그냥 쓰레기값+1이 되어 똑같이 아무 의미 없는 값을 가리키게 된다.
알찬 스터디 시간이었다... 붐업
참고
https://velog.io/@alslahdk/C-STL-linked-list
https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=picbuddy&logNo=80032246219
