[C++] 백준 1406: 에디터

문제 이해

- 한 줄로 된 에디터를 구현하라.

- 에디터는 영어 소문자만 기록이 가능하고, 최대 600,000 글자까지 지원한다.

- 커서는 문장의 맨 앞, 중간, 맨 뒤까지 어디든 위치가 가능하며, 길이가 L인 문자열에서는 L+1가지의 위치에 있을 수 있다.

- 명령어

-- L: 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)

-- D: 커서를 오른족으로 한 칸 옮김 ( 커서가 문장의 맨 뒤이면 무시됨)

-- B: 커서 왼쪽에 있는 문자를 삭제

-- P $: $라는 문자를 커서 왼쪽에 추가

- 커서의 처음 위치는 문장의 맨 뒤이다.

 

<입력>

- 문자열 (길이가 N(1 ~ 100,000, 10^5), 소문자로만 구성됨)

- M: 입력할 명령어의 개수 (1~500,000, 10^5)

- 명령어들

 

<출력>

- 모든 명령어를 수행한 뒤 에디터에 입력되어 있는 문자열을 출력하라.

 

<조건>

- 시간 제한: 0.3초

- 메모리 제한: 512MB

 

 

문제 풀이

처음에는 단순히 문자열의 함수들을 이용해 접근해보았다.

 

c++ string에 내재되어있는 insert()와 erase()를 사용하면 쉽게 구현할 수 있다고 생각해 그대로 코드를 작성해보았다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin>>s;

    int cursor = s.size();

    int m;
    cin>>m;
    while(m--){
        char com;
        cin>>com;

        if(com == 'L'){
            if(cursor > 0){
                cursor--;
            }
        }else if(com == 'D'){
            if(cursor < s.size()){
                cursor++;
            }
        }else if(com == 'B'){
            if(cursor > 0){
                cursor--;
                s.erase(cursor, 1);
            }
        }else if(com == 'P'){
            string tmp;
            cin>>tmp;

            s.insert(cursor, tmp);
            cursor++;
        }
    }
    
    cout<<s;
    return 0;
}

위의 코드는 바로 시간 초과로 틀렸다.

 

 

생각해보니 지금 N의 크기는 10^5인데 반해

시간 제한은 0.3초이다.

그렇다면 시간 복잡도가 O(N^2)만 되어도 시간 초과가 될 수밖에 없다.

 

 

필자도 잘 몰랐는데

string의 insert()함수와 erase()함수는 각각 O(N)의 시간 복잡도를 가진 함수로

명령어의 개수인 m이 10^5이므로 O(m * N)만 되어도 당연히 시간초과일 수밖에 없었다.

 

 

 

그렇기에 while문 안의 명령어들은 사실상 O(1)의 시간복잡도를 가져야만 했다.

 

 

이번에는 커서를 기준으로 왼쪽, 오른쪽을 나누어 stack의 자료형으로 구현해보았다.

vector 자료형이 더 편해 vector를 사용하였으나 원리는 같다.

각각 push_back()과 pop_back()은 O(1)의 시간 복잡도를 가졌기에 쉽게 AC를 받을줄 알았다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin>>s;

    vector <char> left;
    vector <char> right;

    int size = s.size();
    for(int i = 0; i < size; i++){
        left.push_back(s[i]);
    }

    int m;
    cin>>m;
    while(m--){
        char com;
        cin>>com;

        if(com == 'L'){
            if(!left.empty()){
                right.push_back(left.back());
                left.pop_back();
            }
        }else if(com == 'D'){
            if(!right.empty()){
                left.push_back(right.back());
                right.pop_back();
            }
        }else if(com == 'B'){
            if(!left.empty()){
                left.pop_back();
            }
        }else if(com == 'P'){
            char tmp;
            cin>>tmp;
            left.push_back(tmp);
        }
    }
    
    string ans = "";
    while(!left.empty()){
        ans = left.back() + ans;
        left.pop_back();
    }
    while(!right.empty()){
        ans = ans + right.back();
        right.pop_back();
    }

    cout<<ans;
    return 0;
}

과연 이번에는 AC를 받았을까?

 

코드를 읽어보면 알겠지만 시간 초과로 틀렸다!

 

이유는 아래에 답을 출력하기 위해 left와 right를 합치는 과정 속에 있었다.

ans = left.back() + ans;

ans = ans + right.back();

위의 두 코드가 문제였는데

 

left와 right의 크기만큼 반복하는 while문은 O(N)의 시간복잡도를 갖는다.

그렇다면 마찬가지로 while문 안의 명령어는 O(1)의 시간복잡도를 가져야 하는 것이다.

 

그런데 위의 코드 방식은 새로운 문자열을 생성하여 기존의 ans에 대입하기에 O(N)의 시간복잡도를 갖는다.

결국, O(N^2)의 시간복잡도로 시간초과가 되는 것이다!!

 

 

그렇다면 어떻게 해결할 수 있을까?

첫 번째는 ans = ans + "?"; 의 방식을 대신해서 ans += "?";을 쓰는 것이다.

후자의 경우는 처음 코드와 달리 O(1)의 시간복잡도를 가져 시간제한에 걸리지 않는다.

 

두 번째는 push와 pop을 이용하는 방식이다.

 

 

필자는 두 가지 방법을 혼용하여 해결하였다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin>>s;

    vector <char> left;
    vector <char> right;

    int size = s.size();
    for(int i = 0; i < size; i++){
        left.push_back(s[i]);
    }

    int m;
    cin>>m;
    while(m--){
        char com;
        cin>>com;

        if(com == 'L'){
            if(!left.empty()){
                right.push_back(left.back());
                left.pop_back();
            }
        }else if(com == 'D'){
            if(!right.empty()){
                left.push_back(right.back());
                right.pop_back();
            }
        }else if(com == 'B'){
            if(!left.empty()){
                left.pop_back();
            }
        }else if(com == 'P'){
            char tmp;
            cin>>tmp;
            left.push_back(tmp);
        }
    }
    
    string ans = "";
    while(!left.empty()){
        right.push_back(left.back());
        left.pop_back();
    }
    while(!right.empty()){
        ans += right.back();
        right.pop_back();
    }

    cout<<ans;
    return 0;
}

 

드디어 AC를 받을 수 있었다!!!

 

stack을 통해 푸는 문제였지만,

 

string에 내재된 함수의 시간복잡도에 대해 배울 수 있었고,

string 자료형의 더하기 연산 속 시간복잡도도 배울 수 있었던 좋은 문제였다!!!