[BOJ 9935 // C++] 문자열 폭발

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 9935번 문제인 문자열 폭발이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/9935

9935번: 문자열 폭발

이 문제에서는 주어진 긴 문자열 s1에서 짧은 문자열 s2가 존재하지 않을 때까지 지우는 문제이다.

 

예를 들어, 문제의 예제2번을 보면 s1 = 12ab112ab2ab, s2 = 12ab이다.

여기서 바로 눈에 보이는 s2를 표시하면 "12ab"1"12ab"2ab 와 같이되고, 이 부분을 지우면 12ab가 남는다.

여전히 s1에 s2가 존재하므로, 다시 s1을 없애주면 s1은 빈 문자열이 된다.

 

처음 이 문제를 보았을 때, 문자열 해싱을 이용해 이 문제를 해결할까 고민했지만 해싱을 하지 않아도 풀 수 있을 것 같은 숫자범위(s2가 36자 이하)를 보고 다른 방법을 생각하로 했다. 아래는 처음 고안한 코드이다.

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::string;

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int s1len = s1.length(), s2len = s2.length();
    int i = 0;
    while (i<s1len - s2len + 1 and s1len>=s2len) {
        bool chk = 1;
        for (int j = 0;j < s2len;j++) {
            if (s1[i + j] != s2[j]) {
                chk = 0;
                i += (j==0)?1:j;
                break;
            }
        }
        if (chk) {
            s1.erase(i, s2len);
            s1len -= s2len;
            if (i >= s2len - 1) i -= s2len - 1;
            else i = 0;
        }
    }
    if (s1len == 0) cout << "FRULA";
    else cout << s1;

    return 0;
}

이 코드는 다음과 같이 작동한다.

 

1) erase를 이용하여 s1을 탐색해나가며 s2가 나올 때마다 s1에서 s2부분을 지워주고,

2) 문자열을 지웠을 때 s1에서 탐색하던 지점을 (s2.length()-1)만큼 (그만큼 앞에 글자가 없으면 s1[0]으로) 이전으로 돌아가 계속 s1에서 s2를 찾는다.

3) 탐색하는 지점부터 남은 s1의 글자가 s2보다 적으면 (또는 s1이 s2보다 짧아지면) 탐색을 중단한다.

 

이 코드로 문제를 충분히 통과할 수 있을 것으로 기대했으나, 실제로는 TLE를 받게 되었다. 그 이유가 무엇일까?

 

위 코드는 몇몇 케이스를 수월하게 통과할 수는 있겠지만, aaaaaa...bcdefghijkbcdefghijkbcdefghijk 에서 abcdefghijk를 찾는 꼴의 탐색에는 매우 약하다는 문제점이 있다. abcdefghijk를 찾을 때마다 a밖에 없는 앞부분으로 한참 이동하게 되고, a 하나당 조사를 여러 번 하게 되는 것이다. 그러므로 이 코드는 TLE가 나는 경우가 존재한다.

 

 

따라서 시간을 더욱 절약하기 위해서는 위와 같은 경우의 불필요한 탐색을 줄여줄 필요가 있다. 이를 위해, 앞에 지나간 문자에 이 글자가 s2의 몇 번째까지 매칭되었는지 확인할 수 있는 숫자를 같이 기록할 수 있다면 위 코드의 성능은 많이 개선될 것이다. 특히, 이 문제의 조건에서 s2는 중복 문자가 들어있지 않은 문자열이므로, 이와 같은 방향의 성능 개선은 어렵지 않은 편이다.

 

다음은 위의 코드의 작동방식을 개선한, 제출한 코드에 사용한 알고리즘이다.

 

1) 스택의 역할로 사용할 deque<char,int>를 하나 만든다.

2) s1을 첫 문자부터 읽으면서 deque에 { (현재 문자), (현재까지 매칭된 길이) } 를 계속 넣어준다.

3) 현재까지 매칭된 길이가 s2의 길이와 같아진다면, deque에서 s2의 길이만큼의 원소를 빼낸다.

4) s1의 모든 문자를 읽었다면, First In First Out 순으로 deque에서 문자들을 꺼내 출력한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <deque>
#include <vector>
using std::cin;
using std::cout;
using std::string;
using std::deque;
using std::pair;

deque<pair<char, int>> dq;

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string s1, s2;
    cin >> s1 >> s2;
    int s1len = s1.length(), s2len = s2.length();
    for (int i = 0;i < s1len;i++) {
        if (dq.empty()) { // deque이 빈 경우: deque의 top에서 정보를 읽어올 수 없으므로 따로 처리
            if (s1[i] == s2[0]) {
                dq.push_back({ s1[i], 1 });
            }
            else dq.push_back({ s1[i],0 });
        }
        else { // deque에 원소가 있는 경우 top에서 정보를 읽어온다.
            int x = dq.back().second;
            if (s1[i] == s2[x]) { // 앞에서 나온 문자에 이어서 s2를 적어나가는 경우
                dq.push_back({ s1[i],x + 1 });
            }
            else if (s1[i] == s2[0]) { // s2의 시작점이 될 수 있는 경우
                dq.push_back({ s1[i],1 });
            }
            else dq.push_back({ s1[i],0 }); // 아무 것도 아닌 경우
        }
        int x = dq.back().second;
        if (x == s2len) { // deque에서 s2를 찾으면 deque에서 s2의 길이만큼 원소를 제거
            for (int k = 0;k < s2len;k++) dq.pop_back();
        }
    }
    // 답 출력
    if (dq.empty()) cout << "FRULA";
    else {
        while (!dq.empty()) {
            char x = dq.front().first; dq.pop_front();
            cout << x;
        }
    }
}