[백준 3111] 검열

 아직 도전하기에는 쉬운 문제는 결코 아닌 듯 했다.

 2개의 Stack을 사용하여, 하나는 왼쪽부터 검사 또 다른 하나는 오른쪽부터 검사를 하여

 없애고자 하는 문자열을 모두 없애는 기능을 구현하는 것인데,

 

 필자의 소스코드에는 왼쪽과 오른쪽을 합쳐

 없애야 하는 알파벳을 사라지게 하는 부분을

 아직 구현을 하지 못해 contest solution을 올렸다.

http://hsin.hr/2009/index.html

위 사이트에 들어가면 다양한 Testcase를 제공하니

반례를 찾을 때 매우 유리하다.

출처 : https://www.acmicpc.net/problem/3111

문제

김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다.

상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모두 없애려고 한다.

1. T에 A가 없으면 알고리즘을 종료한다.
2. T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.
3. T에 A가 없으면 알고리즘을 종료한다.
4. T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.
5. 1번으로 돌아간다.

상근이는 마을을 지배해야하기 때문에, 검열을 할 시간이 없다. 상근이의 검열을 대신해주는 프로그램을 작성하시오. 

입력

첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다.

출력

검열을 한 이후의 텍스트를 출력한다.

예제 입력 1

aba
ababacccababa

예제 출력 1

bacccab

소스코드 (미구현)

#include<iostream>
#include<string>
#include<stack>
#include<algorithm>
 
using namespace std;
 
string t, a;
int l = 0, r;
stack<char> left_stack, right_stack;
 
void left_side(int);
void right_side(int);
void done();
void supervise(int);
 
string ReplaceAll(std::string str, const std::string& from, const std::string& to) {
    size_t start_pos = 0;
    while ((start_pos = str.find(from, start_pos)) != std::string::npos) {
        str.replace(start_pos, from.length(), to);
        start_pos += to.length(); 
    }
    return str;
}
 
void done() {
    string ans;
 
    while (!left_stack.empty()) {
        right_stack.push(left_stack.top());
        left_stack.pop();
    }
 
    while (!right_stack.empty()) {
        ans += right_stack.top();
        right_stack.pop();
    }
 
    ans = ReplaceAll(ans, a, "");
 
    cout << ans;
    system("pause");
    exit(0);
}
 
void left_side(int len) {
    string tmp;
    for (int i = l; i < t.size(); i++) {
        left_stack.push(t[i]);
        int ls = left_stack.size();
        tmp += t[i];
        if ((tmp.size() >= len)) {
            if (tmp.substr(tmp.size() - len, tmp.size()).compare(a) == 0) {
                tmp.replace(tmp.size()-len, tmp.size(), "   ");
                for (int k = 0; k < len; k++)
                    left_stack.pop();
                l++;
                return;
            }
        }
        l++;
    }
}
 
void right_side(int len) {
    string tmp;
    for (int i = r - 1; i >= 0; i--) {
        right_stack.push(t[i]);
        int rs = right_stack.size();
        tmp += t[i];
        if ((tmp.size() >= len)) {
            if (tmp.substr(tmp.size() - len, tmp.size()).compare(a) == 0) {
                tmp.replace(tmp.size()-len, tmp.size(), "   ");
                for (int k = 0; k < len; k++)
                    right_stack.pop();
                r--;
                return;
            }
        }
        r--;
    }
}
 
void supervise(int len) {
    while (1) {
        if(!t.find(a))
            done();
        left_side(len);
        right_side(len);
    }
}
 
int main() {
    cin >> a >> t;
    r = t.size();
    supervise(a.size());
    return 0;
}

소스코드 ( contest solution )

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
#define MAXT 300000
#define MAXA 25
 
int lenA, lenT;
char T[MAXT + 1];
char A[MAXA + 1];
 
struct stack {
    int top;
    char x[MAXT + 1];
    char w[MAXA];
 
    void init(char *A) {
        for (int i = 0; i < lenA; ++i)
            w[i] = A[lenA - 1 - i];
        top = 0;
    }
 
    int add(char c) {
        int ret = 0;
        x[top++] = c;
        if (top >= lenA) {
            ret = 1;
            for (int i = 0; i < lenA; ++i)
                if (x[top - i - 1] != w[i])
                    ret = 0;
            if (ret) top -= lenA;
        }
        return ret;
    }
} L, R;
 
int main(void) {
    cin >> A;
    lenA = strlen(A);
    cin >> T;
    lenT = strlen(T);
    L.init(A);
    reverse(A, A + lenA);
    R.init(A);
 
    int idx = 0;                            // 현재 idx 
    int lpos = 0, dpos = lenT - 1;            // 왼쪽 오른쪽 길이 
    while (lpos <= dpos){
        if (idx == 0) 
            idx ^= L.add(T[lpos++]);
        else 
            idx ^= R.add(T[dpos--]);
    }
    while (L.top)
        R.add(L.x[--L.top]);
 
    while (R.top)
        cout<< R.x[--R.top];
 
    return 0;
}

출처 : http://hsin.hr/2009/index.html

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.