들어가는 말
간단한 한 문장 에디터를 출력하는 문제다. 문제가 stack에 분류되어 있기도 했고 본래는 stack 혹은 list로 풀어야 하지만 나는 제일 먼저 vector로 풀고 싶었다. 시간초과가 날 것을 알고 있었지만 그래도 vector로 풀고 싶었다...
처음에는 받는 문자열에 공백이 포함되어 있기에 getline으로 넣어줬다. 그러나 D에서 문제가 생기고 다른 사람의 풀이를 찾아보자 그럴 필요가 없다는 것을 알아차렸다(물론 getline으로 풀어도 큰 문제는 없다. 나한테 생긴 오류는 B의 idx에 있었으니...). 뿐만 아니라 나는 만일 idx가 무시 가능한 위치에 있다면 continue하도록 if절을 넣어줬으나 그럴 필요 없이 그냥 무시 가능한 위치가 아니라면 조건문을 바로 쓰면 되는 것을 알아차렸다.
코드 설명
일단 초기 문장을 받는다. idx의 값은 초기 문장의 길이다. 왜냐하면 커서가 문장의 맨 끝에 있기 때문이다(커서는 0부터 시작한다). 문장을 벡터에 넣어준 다음 명령어의 수 n을 받는다.
그리고 n만큼 for문을 돌려서 order을 받는데, 만일 order가 L이고 idx가 0(제일 처음)이 아닐 경우 커서를 왼쪽으로 옮겨야 하기 때문에 idx를 --해준다.
만일 order가 D이고 idx가 벡터의 사이즈가 아니라면(문장의 맨 끝에 있지 않다면) idx를 ++해준다.
만일 order가 B이고 idx가 0이 아니라면(커서가 문장의 맨 앞에 있지 않다면) idx-1에 있는 원소를(커서의 왼쪽에 있는 원소를) 지워준다. 그리고 여기서 idx를 --해줘야 한다. 왜냐하면 원소 하나를 지웠기 때문에 인덱스도 자연히 하나가 줄어들기 때문이다. 나는 이 부분을 놓쳐서 자꾸만 벡터 오류가 났다.
마지막으로 order이 P라면, 이는 문자 하나를 더 더하라는 의미이니까 add 문자를 하나 받아서 idx위치에 add를 넣고 idx를 ++해주면 된다.
그리고 완성된 벡터를 출력해주면 끝!
코드
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
vector<char> v;
string s = "";
/*아직 어떤 문자열도 받지 않았으니 현재 커서의 위치는 0이다.*/
int idx = 0;
int n = 0;
char order;
//int len = v.size();
/*초기 문장을 받는다.*/
cin >> s;
/*현재 커서의 위치는 맨 마지막에 위치해 있다.*/
idx = s.length();
/*받은 문장을 벡터와 스택에 넣는다.*/
for (auto s1 : s) {
v.push_back(s1);
}
/*명령어의 수를 받는다.*/
cin >> n;
/*명령어의 수 만큼 for문을 돌린다.*/
for (int i = 0; i < n; i++) {
cin >> order;
/*커서를 왼쪽으로 옮길 경우 커서가 제일 앞에 있지 않을 경우에만 idx를 --해준다.*/
if (order == 'L') {
if (idx != 0) {
idx--;
}
}
/*커서를 오른쪽으로 옮길 경우 커서가 문장 맨 뒤에 있지 않을 경우에만 idx를 ++해준다.*/
if(order == 'D'){
if (idx != v.size()) {
idx++;
}
}
/*커서의 왼쪽에 있는 문자를 하나 지워줄 경우, idx-1(커서는 해당 문자의 오른쪽에 있다)의 문자를 지워준 후에
idx를 --해준다(문자 하나가 지워졌기 때문에)*/
if (order == 'B') {
if (idx != 0) {
v.erase(v.begin() + (idx - 1));
idx--;
//len = v.size();
}
}
/*커서의 왼쪽에 문자를 넣을 경우, 넣고자 하는 문자를 하나 받아서 커서의 위치에 넣어주고 idx를 ++해주면 된다.*/
if (order == 'P') {
char add;
cin >> add;
v.insert(v.begin() + idx, add);
idx++;
//len = v.size();
}
}
for (auto vv : v) {
cout << vv;
}
}시간 초과 이유
벡터를 이용했을 때 시간 초과가 나는 이유는 간단하다. 벡터는 크기를 동적으로 이용하지만, insert, erase를 하는 경우 재할당의 비용이 크기 때문이다.
insert를 하면 해당 공간을 비워주고 뒤의 원소들을 미뤄야 하고 erase를 하면 빈 공간이 생기지 않도록 뒤의 원소를 땡겨 와야 하기에 시간이 걸린다.
해당 문제의 경우 insert, erase가 여러 번 나올 수 있는데, 계속해서 insert, erase에서 시간이 크게 나오니 시간 초과가 나오는 것이다.
참고
