1406. 에디터

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

걸린 시간: 33m28s

문제

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

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

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

문제 접근 방법

커서를 앞뒤로 옮기는 것은 문제가 안되나 중간에 새로운 문자를 추가해야되기 때문에 연결리스트를 떠올렸다. 구현을 해야되나 했는데 C++ STL에 list가 있었다. STL list는 익숙하지가 않아서 reference에서 함수들 봐가면서 필요한 것들을 골라 사용했다. 그 중에 문자 삽입을 위한 insert 그리고 삭제를 위해 erase를 사용했다.

커서의 앞뒤 이동은 이터레이터를 ++/--해주면 되고 추가도 insert로 간단히 가능했다. erase 부분에서 코드를 처음에는 아래와 같이 했었는데 segfault가 나왔다.

1--it;
2str.erase(it);

그래서 뭐가 문제일까 하다가, 아마 이터레이터가 가리키고 있는 부분이 지워지는게 문제가 아닐까 하고 아래처럼 임시 변수에 저장해서 했더니 잘 작동했다.

1auto temp = it;
2--temp;
3str.erase(temp);

C++ 코드

1#include <bits/stdc++.h>
2using namespace std;
3
4#define ios cin.tie(NULL), ios_base::sync_with_stdio(false)
5#define endl '\n'
6
7int main(){
8  ios;
9  list<char> str;
10  string s;
11  cin >> s;
12  const int SIZE = s.size();
13  for(int i=0; i<SIZE; ++i) {
14    str.push_back(s[i]);
15  }
16
17  // cursor is at the end
18  list<char>::iterator it = str.end();
19  int m;
20  cin >> m;
21  while(m--) {
22    char ch; 
23    cin >> ch;
24    if(ch == 'L') {
25      if(it != str.begin()) --it;
26    } else if(ch == 'D') {
27      if(it != str.end()) ++it;
28    } else if(ch == 'B') {
29      if(it != str.begin()) {
30        auto temp = it;
31        --temp;
32        str.erase(temp);
33      }     
34    } else if(ch == 'P') {
35      char addCh; 
36      cin >> addCh;
37      str.insert(it, addCh);
38    }
39  }
40
41  // print answer
42  list<char>::iterator ans = str.begin();
43  while(ans != str.end()) {
44    cout << *ans;
45    ++ans;
46  }
47  cout << endl;
48  return 0;
49}

시간 복잡도

초기 문자열을 리스트에 추가 - O(S), S = 문자열 길이
M개의 커맨드 연산 - O(M)
최종 문자열 출력 - O(S'), S' = 문자열 길이
최종 시간 복잡도: O(S + M + S')

공간 복잡도

초기 문자열을 담고 있는 리스트 - O(S), S = 문자열 길이
각 커맨드의 연산 종료 후 최종 문자열을 담고 있는 리스트 - O(S'), S' = 최종 문자열의 길이
최종 공간 복잡도: O(S + S')