[C++]3111번: 검열

요약

처음에 문제 이해가 안갔는데, 앞뒤앞뒤 이렇게 제거한다는 얘기였다

stack 2개를 사용하여 문자열 그대로 / 리버스 문자열 2개를 대상으로 앞 뒤 제거를 진행하였다.

서로 제거 범위가 겹치지 않도록 index를 저장해서 관리해줘야 한다!

풀이과정

첫시도 - 스택 활용(시간초과)

1. 검열 문자열과, 신문 문자열을 뒤집어서도 저장 - right stack을 위해서

2. left stack point + right stack point의 합이 신문 문자열의 크기보다 작은 동안만 stack에 넣으며 검사를 진행

3. 앞뒤로 문자열을 나누었기 때문에, 마지막에 이 문자열을 합치면서 나오는 검열 문자열이 있는지 한 번 검사 - 겸사겸사 문자열을 합치기 위해 right stack에 있는 것들을 left stack에 넣으면서 검사하기

4. left stack에 들어가 있는 문자열을 출력

//https://www.acmicpc.net/problem/3111
using namespace std;

#include <iostream>
#include <stack>
#include <string>

#define     left    0
#define     right   1

stack<char> s[2];
int p[2];
int wsize, psize;
string word[2];
string paper[2];

// 현재 stack 상단에 검열 문자열이 있는지 확인
bool isCensored(stack<char> s, string &word)
{
    //검열 문자열보다 stack 크기가 작음 - false
    if(s.size() < word.size()) return false;
    for(int i = word.size()-1; i >= 0; i--)
    {
        char temp = s.top();    s.pop();
        if(temp != word[i]) return false;   
    }
    return true;
}

// 문자열에서 검열 문자열의 크기만큼 pop
void popWord(stack<char> &s)
{
    for(int i = 0; i < wsize; i++)
        s.pop();
}

// stack의 값을 뒤집어서 string으로 반환
string stackReverse(stack<char> &s)
{
    string result;
    while(!s.empty())
    {
        result = s.top() + result;
        s.pop();
    }
    return result;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> word[left] >> paper[left];
    wsize = word[left].size();
    psize = paper[left].size();

    for(int i = wsize-1; i >= 0; i--)
    {
        word[right] += word[left][i];
    }
    for(int i = psize-1; i >= 0; i--)
    {
        paper[right] += paper[left][i];
    }
    while(p[left] + p[right] < psize)
    {
        for(int i = 0; i < 2; i++)  // i(0) : left, i(1) : right
        {
            while(p[left]+p[right] < psize)    
            {
                // if(i == 0) cout << "left " << p[i] << endl; else cout << "right "<< p[i] << endl;
                s[i].push(paper[i][p[i]++]);  //pointer 위치의 paper char 하나를 stack에 push하고 pointer += 1
                // cout << s[i].top() << " ";
                if(isCensored(s[i], word[i]))
                {//검열 문자열 상단에서 발견
                    // cout << word[i] << " detected" << endl;
                    popWord(s[i]);
                    break;
                }
            }
        }
    }
    // right stack 을 left stack으로 몰아넣고 검열 단어가 나오는지 마지막으로 확인
    if(!s[right].empty())
    {
        while(!s[right].empty())
        {
            s[left].push(s[right].top());
            s[right].pop();
            if(isCensored(s[left], word[left]))
            {
                // cout << word[left] << " detected \n";
                popWord(s[left]);
            }
        }
    }

    // left stack의 값 출력
    cout << stackReverse(s[left]) << endl;
}

이전에 비슷하게 푼 문제를 stack으로 풀었는데, stack으로 푸려다가 더 시간이 오래걸리는게 아닌가 생각이 듦
왜냐면, stack 검사도 pop했다가, 검열문자 발견되면 pop하는데 이게 완전히 중복되는 과정이다.
그렇다고 stack을 reference로 참조시키기에는, 검열문자가 발견되지 않을 경우 push하는 불필요한 과정이 들어가고 말음
그래서 stack대신 string으로 바꿨더니 1372ms로 통과(아슬아슬;)

코드

//https://www.acmicpc.net/problem/3111
using namespace std;

#include <iostream>
#include <stack>
#include <string>

#define     left    0
#define     right   1

int p[2];
int wsize, psize;
string word[2];
string paper[2];
string leftright[2];

// 현재 stack 상단에 검열 문자열이 있는지 확인
bool isCensored(string &s, string &word)
{
    int ssize = s.size();
    //검열 문자열보다 크기가 작음 - false
    if(ssize < wsize) return false;
    for(int i = 0; i < wsize; i++)
    {
        if(s[ssize - wsize + i] != word[i]) return false;
    }

    return true;
}

// 문자열에서 검열 문자열의 크기만큼 제거
void popWord(string &s)
{
    s = s.substr(0,s.size()-wsize);
}

// stack의 값을 뒤집어서 string으로 반환
string stackReverse(stack<char> &s)
{
    string result;
    while(!s.empty())
    {
        result = s.top() + result;
        s.pop();
    }
    return result;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> word[left] >> paper[left];
    wsize = word[left].size();
    psize = paper[left].size();

    for(int i = wsize-1; i >= 0; i--)
    {
        word[right] += word[left][i];
    }
    for(int i = psize-1; i >= 0; i--)
    {
        paper[right] += paper[left][i];
    }
    while(p[left] + p[right] < psize)
    {
        for(int i = 0; i < 2; i++)  // i(0) : left, i(1) : right
        {
            while(p[left]+p[right] < psize)    
            {
                // if(i == 0) cout << "left " << p[i] << endl; else cout << "right "<< p[i] << endl;
                leftright[i] += paper[i][p[i]++];
                // cout << s[i].top() << " ";
                if(isCensored(leftright[i], word[i]))
                {//검열 문자열 상단에서 발견
                    // cout << word[i] << " detected" << endl;
                    popWord(leftright[i]);
                    break;
                }
            }
        }
    }

    // cout << leftright[left] << endl << leftright[right] << endl;
    // right stack 을 left stack으로 몰아넣고 검열 단어가 나오는지 마지막으로 확인
    for(int i = leftright[right].size()-1; i >= 0; i--)
    {
        leftright[left] += leftright[right][i];
        if(isCensored(leftright[left], word[left]))
        {
            popWord(leftright[left]);
        }
    }
    cout << leftright[left] << endl;
}

기억할 점

다른 사람의 풀이

substr 대신 leftright에 index를 따로 지정해주는 방법이 있다.
즉, leftright 끝에서 검열 문자열이 발견되는 경우, 이 index를 검열문자열의 크기만큼 앞으로 땡겨버리는 것이다.

l	u	k	a	n	e
0	1	2	3	4	5	6
				b	<<	a

lukane에서 ne가 검열문자열인 경우 index가 6인데, 발견되는 순간 ne의 크기인 2만큼 빼버린다.

그리고 차후 입력을 b의 위치에서부터 하면 자연스럽게 해당 부분이 무시된다.

출력할때도 b까지만 출력하게 하면 된다.

다만 이 방법을 사용하려면 index기반 값 입력이므로 string 대신 vector나 array사용이 필요해 보인다.

(string도 index를 통한 접근이 가능하지만 기존에 미리 특정 크기만큼 할당하는게 어려우므로... -string은 크기 지정 초기화 시 빈 채로 지정이 안돼서 메모리낭비로 보임)