[3111번 검열]-C++

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

간단한 문자열 문제인 줄 알았지만 아무리 생각해도 시간초과가 나올 것 같다는 생각 때문에 어떻게 코드를 짜야할 지 손을 못 댔다. 결국 검색해서 참고했다.

풀이

처음에는 KMP나 트라이를 사용해서 찾는 건가 했지만 최악의 경우인 A = aaa...a(25자), T = aaa...aaaaa(300,000자)인 경우 앞뒤로 계속 찾아야 하는데 시간초과가 날 게 분명했다.

자료구조 덱(deque)을 이용하여 풀어야 하는 문제였다. 덱을 2개 만들어 앞에서부터는 dq_front에 push_back하여 뒤쪽으로 순서대로 추가하면서 A와 같은 문자열이 덱 안에 만들어졌는지 확인한다.

dq_back에는 push_front하여 앞쪽으로 T의 문자열을 끝에서부터 순서대로 추가하면서 A와 같은 문자열이 덱 안에 만들어졌는지 확인한다.

front_idx = 0, last_idx = T.size()-1 로 설정하여 front_idx가 last_idx를 넘어가게 된다면 검사가 끝난 것으로 간주한다.

C++ 코드

#include <bits/stdc++.h>

#define ll long long
#define mid (st+end)/2
using namespace std;
typedef pair<int,int> pint;
typedef vector<int> vint;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int ans;
char A[26], T[300001];
string a, t;
deque<char> dq_front, dq_back;
int front_idx, last_idx;
string res;

void sol() {
	front_idx = 0;
	last_idx = t.size()-1;

	while(front_idx <= last_idx) {
		while(front_idx <= last_idx) {
			bool found = false;
			dq_front.push_back(t[front_idx++]);

			if(dq_front.size() >= a.size()) {
				found = true;
				for(int i=0;i<a.size();++i) {
					if(a[i] != dq_front[dq_front.size()-a.size()+i]) {
						found = false;
						break;
					}
				}
			}
			if(found) {
				for(int i=0;i<a.size();++i) {
					dq_front.pop_back();
				}
				break;
			}
		}

		while(front_idx <= last_idx) {
			bool found = false;
			dq_back.push_front(t[last_idx--]);

			if(dq_back.size() >= a.size()) {
				found = true;
				for(int i=0;i<a.size();++i) {
					if(a[i] != dq_back[i]) {
						found = false;
						break;
					}
				}
			}
			if(found) {
				for(int i=0;i<a.size();++i) {
					dq_back.pop_front();
				}
				break;
			}
		}
	}

	for(int i=0;i<dq_front.size();++i) {
		res.push_back(dq_front[i]);
	}
	for(int i=0;i<dq_back.size();++i) {
		res.push_back(dq_back[i]);
	}

	while(res.find(a) != string::npos) {
		res.erase(res.find(a), a.size());
	}

	printf("%s\n", res.c_str());
	
	return;
}

int main() {
	// ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	scanf("%s", A);
	scanf("%s", T);
	a = string(A);
	t = string(T);
	
	sol();

	return 0;
}

실행결과