[BOJ 1406] 에디터

1406번: 에디터

문제 분석

• string으로 문제를 풀어보려 한다.
• 계획 : 
  커서 : index i
  L : (i=0) 무시 (i≠0) i-=1
  D : (i=length-1) 무시 (i≠length-1) i+=1;
  B : (i≠0) str.erase(i-1);
        (i=0) 무시
  P $: str.insert(i,$)

string str;
int n,last,i;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>str;
    cin>>n;
    i = (int)str.length(); // index i 초기화
    while(n--){
        char cmd;
        cin>>cmd;
        if(cmd == 'L'){
            if(i!=0){
                i -=1;
            }else continue;
        }
        else if(cmd == 'D'){
            if(i!=str.length()){
                i +=1;
            }else continue;
        }
        else if(cmd == 'B'){
            if(i!=0){
                str.erase(i-1,1);
                i -=1;
            }else continue;
        }
        else{
            string c;
            cin>>c;
            str.insert(i, c);
            i+=1;
        }
    }
    cout<<str<<"\n";
    return 0;
}

 

시간제한이 0.3초라는 걸 염두하지 않은 코드 였다...
위 코드는 string, 즉 char형 배열을 기반으로 짜여진 코드이므로 삽입/삭제시에 상당한 시간이 소모된다.
고로 당연히 시간초과가 났다. 이에 삽입/삭제에 효율적인 <list>를 이용해 보고자 했다.

계획: 
string의 각 char을 list에 추가
커서의 역할을 index i 대신 iterator iter로
나머지 논리는 string기반 코드와 같다.

#include <iostream>
#include <list>

using namespace std;

list<char> str;
string in;
int n;
list<char>::iterator iter;

int main() {
    cin >> in;
    cin >> n;

    for (int i = 0; i < in.length(); i++) {
        str.push_back(in[i]);
    }
    iter = str.end();
    while (n--) {
        char cmd;
        cin >> cmd;
        if (cmd == 'L') {
            if (iter != str.begin())
                iter--;
        } else if (cmd == 'D') {
            if (iter != str.end())
                iter++;
        } else if (cmd == 'B') {
            if (iter != str.begin()) {
                iter--;
                iter = str.erase(iter);
            }
        } else if (cmd == 'P') {
            char c;
            cin >> c;
            str.insert(iter, c);
        }
    }
    for (iter = str.begin(); iter != str.end(); iter++)
        cout << *iter;
    return 0;
}

느낀점

• 이 코드를 짤때, 중간과정을 검정한답시고 iter가 처음 부터 끝까지 살펴보는 코드를 while문 안에 넣었다.
  문제는 <list>를 살펴보는 iterator를 iter로 사용해서 계속 iter가 마지막 원소(ending 노드 직전 노드)로 초기화 되어 iter가 제대로 이동하지않았다는 점이다.
  이 문제를 생각하는데 꽤 오랜시간이 걸렸고,(사실 친구가 코드보고는 알려줬다...) 이에 스스로 자책하게 됐다.
• 나머지 로직은 처음 생각한대로 옳은 로직이었다.

시간 복잡도

• 삽입/삭제 연산  → O(1)
• while문 n번 반복 → O(n)
  ➣ O(n)