백준 3111 검열

 

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

3111번: 검열

문자열 T에서 처음 등장하는 문자열 A, 마지막으로 등장하는 A를 찾아 A가 등장하지 않을 때까지 삭제하는 문제다.

양방향으로 탐색을 해야 하기 때문에 스택이 두 개 필요하다.

 

시간 초과(틀린 풀이) / 맞는 풀이는 아래에

1. 스택 left, right를 준비하고, 문자열 T를 right에 모두 삽입한다.

2. left  <- right 이동시키면서 A가 나오는지 확인한다.

2-1. A가 존재한다면, 삭제하고 방향을 바꾼다(left -> right)

2-2. A가 존재하지 않는다면, 과정을 중단한다.

3. 남은 문자열을 출력한다.

 

시간초과가 나오는 이유 : 

문자열 T는 최대 길이가 30만이고, 문자열 A의 길이는 최대 25까지 가능하다.

위의 풀이의 경우, A의 길이가 1이라면 최악의 경우 T의 길이가 1씩 줄어들며 양쪽 스택을 30만 번 이동하게 된다.

러프하게 계산해보면

30만*1 + (30만 -1)*2 + (30만 - 2)*3 +.... + (30만 - (30만 - 1) )*1으로 약 900억의 계산량이 필요하다.

O(N^2)의 알고리즘에 N = 300,000

 

 

덱(Deque)이 필요하다.

위의 풀이가 시간 초과가 나는 이유는 방향을 바꿀 때마다, 탐색의 시작점인 문자열의 처음과 마지막으로 탐색 시작점을 바꿔야 하기 때문이다.

이때, 두 스택 사이 덱을 넣어 [스택 - 덱 - 스택] 구성을 만들면 덱을 통해 탐색 시작점을 찾기 수월해진다.

덱으로부터 나오는 문자(char)가 A의 시작 문자이거나 마지막 문자인 경우만 A가 존재하는지 확인하면 되기 때문에 효율적이다.

양쪽 스택은 vector로 구성하여 인덱스로 접근하였고 불필요한 pop + push를 줄였다.

최종 답안 (일 뻔했다)

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <vector>
#include <deque>
bool good_to_erase(const vector<char>& V, const string& S){
    int diff = V.size() - S.size();
    for(int i = 0; i < S.size(); i++){
        if(V[diff + i] != S[i]) return false;
    }
    return true;
}

int main(){
    fio;
    string A, T; cin >> A >> T;
    //reverse_A : A역순 구하기
    deque<char> dq;
    for(int i=0; i<T.size(); i++){
        dq.push_back(T[i]);
    }
    string reverse_A;
    for(int i = A.size()-1; i>=0; i--){
        reverse_A.push_back(A[i]);
    }
    vector<char> left, right;
    char left_trigger = reverse_A[0];
    char right_trigger = A[0];
    int th_size = A.size();
    //1. 첫 번째 거르기
    bool dir = true;
    while(!dq.empty()){
        if(dir){//to the left
            char now = dq.front();
            dq.pop_front();
            left.push_back(now);
            if(now == left_trigger){
                if(left.size() >= th_size){//가능성 있는 사이즈다
                    if(good_to_erase(left, A)){//나왔다 
                        //지우자
                        for(int e = 0; e < th_size; e++){
                            left.pop_back();
                        }
                        //방향 바꾸자
                        dir ^= 1;
                    }
                }
            }
        }else{//to the right
            char now = dq.back();
            dq.pop_back();
            right.push_back(now);
            if(now == right_trigger){
                if(right.size() >= th_size){//가능성 있는 사이즈다
                    if(good_to_erase(right, reverse_A)){//나왔다 
                        //지우자
                        for(int e = 0; e < th_size; e++){
                            right.pop_back();
                        }
                        //방향 바꾸자
                        dir ^= 1;
                    }
                }
            }
        }
    }
    //2. 두 번째 거르기
    while(!left.empty() && !right.empty()){
        if(dir){//to the left
            char now = right.back();
            right.pop_back();
            left.push_back(now);
            if(now == left_trigger){
                if(left.size() >= th_size){//가능성 있는 사이즈다
                    if(good_to_erase(left, A)){//나왔다 
                        //지우자
                        for(int e = 0; e < th_size; e++){
                            left.pop_back();
                        }
                        //방향 바꾸자
                        dir ^= 1;
                    }
                }
            }
        }else{//to the right
            char now = left.back();
            left.pop_back();
            right.push_back(now);
            if(now == right_trigger){
                if(right.size() >= th_size){//가능성 있는 사이즈다
                    if(good_to_erase(right, reverse_A)){//나왔다 
                        //지우자
                        for(int e = 0; e < th_size; e++){
                            right.pop_back();
                        }
                        //방향 바꾸자
                        dir ^= 1;
                    }
                }
            }
        }
    }
    //3. 마무리
    while(!left.empty()){
        right.push_back(left.back());
        left.pop_back();
    }
    //print
    while(!right.empty()){
        cout << right.back();
        right.pop_back();
    }

    return 0;
}

업로드하려고 보니 길다...(사실문제 풀 때 귀찮아서 그냥 넘겼다)

어차피 손볼 거 일찍 해놓고 문제 풀걸 그랬다..

아직 눈에 띄는게 많지만....

 

최종 답안 (Refactored)

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <vector>
#include <deque>
bool good_to_erase(const vector<char>& V, const string& S){
    int diff = V.size() - S.size();
    for(int i = 0; i < S.size(); i++){
        if(V[diff + i] != S[i]) return false;
    }
    return true;
}
bool if_then(vector<char>& V, const string& A){
    if(V.size() >= A.size()){
        if(good_to_erase(V, A)){
            for(int e = 0; e < A.size(); e++){
                V.pop_back();
            }
            return true;
        }
    }
    return false;
}
int main(){
    fio;
    string A, T; cin >> A >> T;
    //reverse_A : A역순 구하기
    deque<char> dq;
    for(int i=0; i<T.size(); i++){
        dq.push_back(T[i]);
    }
    string reverse_A;
    for(int i = A.size()-1; i>=0; i--){
        reverse_A.push_back(A[i]);
    }
    vector<char> left, right;
    char left_trigger = reverse_A[0];
    char right_trigger = A[0];
    int th_size = A.size();
    //1. 첫 번째 거르기
    bool dir = true;
    while(!dq.empty()){
        if(dir){//to the left
            char now = dq.front();
            dq.pop_front();
            left.push_back(now);
            if(now == left_trigger){
                if(left.size() >= th_size){//가능성 있는 사이즈다
                    if(if_then(left, A)){
                        dir ^= 1;
                    }
                }
            }
        }else{//to the right
            char now = dq.back();
            dq.pop_back();
            right.push_back(now);
            if(now == right_trigger){
                if(right.size() >= th_size){//가능성 있는 사이즈다
                    if(if_then(right, reverse_A)){
                        dir ^= 1;
                    }
                }
            }
        }
    }
    //2. 두 번째 거르기
    while(!left.empty() && !right.empty()){
        if(dir){//to the left
            char now = right.back();
            right.pop_back();
            left.push_back(now);
            if(now == left_trigger){
                if(left.size() >= th_size){//가능성 있는 사이즈다
                    if(if_then(left, A)){
                        dir ^= 1;
                    }
                }
            }
        }else{//to the right
            char now = left.back();
            left.pop_back();
            right.push_back(now);
            if(now == right_trigger){
                if(right.size() >= th_size){//가능성 있는 사이즈다
                    if(if_then(right, reverse_A)){
                        dir ^= 1;
                    }
                }
            }
        }
    }
    //3. 마무리
    while(!left.empty()){
        right.push_back(left.back());
        left.pop_back();
    }
    //print
    while(!right.empty()){
        cout << right.back();
        right.pop_back();
    }

    return 0;
}