BOJ 1406 - 에디터

• 10^5 이하의 길이인 초기 문자열이 주어지고 쿼리의 개수 N(N<=5*10^5)가 주어졌을 때 모든 쿼리를 마친 후 문자열을 출력하는 문제이다.

문제 풀이

• 처음에 그냥 vector를 이용해 처리하면 될거라 생각했는데 vector의 경우 insert, erase 함수가 Linear in the number of elements in vector(element shifting, resizing까지 고려해야한다.)이기 때문에 TLE를 받았다.

• insert, erase가 Linear in the number of elements inserted/erased인 list를 사용해야 통과할 수 있다.

소스코드

#include<iostream>
#include<cstdio>
#include<string>
#include<list>
using namespace std;
typedef list<char>::iterator iter;
int main()
{
	int n;
	string org;
	getline(cin, org);
	list<char> s;
	for(int i=0;i<org.length();i++) s.push_back(org[i]);
	iter idx=s.end();
	scanf("%d", &n);
	for(int i=0;i<n;i++){
		char c;
		scanf("\n%c", &c);
		if(c=='L'){
			if(idx!=s.begin()) --idx;
		}
		else if(c=='D'){
			if(idx!=s.end()) ++idx;
		}
		else if(c=='B'){
			if(idx!=s.begin()) idx=s.erase(--idx);
		}
		else{
			char p;
			scanf(" %c", &p);
			s.insert(idx, p);
		}
	}
	for(idx=s.begin();idx!=s.end();++idx) printf("%c", *idx);
}

풀고나서

• 사실 list는 한 번도 쓰지 않았던 STL이라 찾으며 푸느라 화가 났었다. vector의 경우 iterator에서 바로 n만큼 연산하여 원하는 위치에 access할 수 있었는데 list가 그게 안되었기 때문이다.(쿼리 문자열 처리도 한 몫 했다.)

• vector는 random access iterator라 ++, -- 연산 뿐만 아니라 +, +=와 같은 연산자들도 다 오버로딩이 되어있다. 하지만 list는 bidirectional iterator이기 때문에 ++, -- 연산자만 오버로딩이 되어있다. 그래서 iter+=idx와 같은 연산이 되지 않았던 것이다.(list<char>이라 안되나 하는 생각에 삽질을 했다..)

• 추가적으로 insert함수를 쓰면서 알게 된 것이 있는데,
  insert(iter, val)을 하면 list와 vector 모두 iter 이전에 val이 추가되는 것은 맞지만 list의 경우 함수가 끝난 후 iter가 이전에 가리키던 값을 그대로 가리키고 vector의 경우 iter가 추가된 값을 가리킨다.(여러 개가 추가되었으면 그 중 첫 번째 즉, iter가 이전의 위치를 유지한다.)

`vector`, `list`에서의 `insert` 함수 예시

#include<cstdio>
#include<vector>
#include<list>
using namespace std;

int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	vector<int>::iterator it;
	it=v.begin()+1;
	printf("%d\n", *it);
	v.insert(it, 4);
	printf("%d\n", *it);
	for(it=v.begin();it!=v.end();++it) printf("%d ", *it);
	printf("\n");
	
	list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	list<int>::iterator lit;
	lit=l.begin();
	lit++;
	printf("%d\n", *lit);
	l.insert(lit, 4);
	printf("%d\n", *lit);
	for(lit=l.begin();lit!=l.end();++lit) printf("%d ", *lit);
	printf("\n");
}

실행 결과는 아래와 같다.

2
4
1 4 2 3
2
2
1 4 2 3

• 이번 기회에 list를 쓰면서 iterator개념도 다시 한 번 짚어보게 된 것 같다.