[BOJ 3111 // C++] 검열

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

 

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

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

3111번: 검열

검열하려는 단어 A의 길이는 25 이하이므로 같은 길이의 부분문자열 S와 A가 서로 같은지 확인하는 데에 걸리는 시간은 상수시간으로 생각할 수 있다.

 

문제에서 주어진 반복작업을 하면서, 이전에 확인했던 범위까지 확인을 다시 하는 것은 연산의 낭비가 심하므로 스택 등과 같이 이미 확인한 부분에 대한 재확인 작업을 반복하지 않는 것으로 문제를 해결할 수 있다.

 

오른쪽 끝의 글자를 하나씩 확인할 때는 순서가 뒤집힌 문자열을 집어넣는 스택과 A를 뒤집은 revA가 서로 같은지 확인하는 것으로 구현하는 것으로 문제를 편하게 해결할 수 있다.

 

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

#include <iostream>
#include <string>
#include <algorithm>
#include <deque>
using namespace std;

int Alen;
string A, revA;
string L, T, R;
deque<char> dq;

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

	bool chk = 1;
	cin >> A >> T;
	revA = A;
	reverse(revA.begin(), revA.end());
	Alen = A.length();
	for (auto l : T) dq.push_back(l);
	while (1) {
		while (1) {
			if (L.length() >= Alen) {
				if (L.substr(L.length() - Alen, Alen) == A) {
					for (int i = 0; i < Alen; i++) L.pop_back();
					break;
				}
			}
			if (!dq.empty()) {
				L.push_back(dq.front());
				dq.pop_front();
			}
			else if (!R.empty()) {
				L.push_back(R.back());
				R.pop_back();
			}
			else {
				chk = 0;
				break;
			}
		}
		
		if (!chk) break;

		while (1) {
			if (R.length() >= Alen) {
				if (R.substr(R.length() - Alen, Alen) == revA) {
					for (int i = 0; i < Alen; i++) R.pop_back();
					break;
				}
			}
			if (!dq.empty()) {
				R.push_back(dq.back());
				dq.pop_back();
			}
			else if (!L.empty()) {
				R.push_back(L.back());
				L.pop_back();
			}
			else {
				chk = 0;
				break;
			}
		}
		if (!chk) break;
	}

	reverse(R.begin(), R.end());
	cout << L << R;
}