[백준]Baekjoon3111(스택 or deque 활용)

문제링크 : https://www.acmicpc.net/problem/3111

풀이

푸느라 상당히 시간이 많이걸린 문제이다 시간초과 , 출력초과가 빡치는 문제이다.

일단 나는 deque를 통해 코드를 작성했다.

deque를 통해 앞에서부터 받을 때는 push_back을 통해

뒤에서부터 받을 때는 push_front를 통해 문자들을 받았다.

문자를 받을 때 마다 누적된 문제들이 검열하는 텍스트 A와 같은지 검사하며

front_index <= last_index :  앞에서부터 시작된 index가 뒤에서 시작한 index를

넘어설 때까지 반복문을 수행하게 된다.

이게 가능한 이유는 문자를 받을 때 마다 전수조사를 해도 30만 * 30 = 900만

정도밖에 안되기 때문에 충분히 검사가 가능한 것이다.

이렇게만 하고 여차저차 풀어서 제출을 하면 출력초과가 걸릴것이다 ㅎㅎ

이렇게 되는 이유는 덱 2개를 합쳤을 때 나타나는 A가 또 생기기 때문이다.

문제가 너무 안풀려서 약간의 편리한 방법을 썼는데

덱에 있는것을 모두 string으로 합친뒤 find함수를 통해 A와 같은것을 찾고

지우는 방식을 택했다.

처음부터 이런식으로 하면 시간초과가 나지만 이렇게 지워질것이 거의 지워진다음

수행하면 find함수 수행 자체는 별로 안일어나기 때문에 시간안에 출력하는것이 가능해진다.

친절하게 주석을 달아놓았으니 참고하길 바란다.

#include <iostream>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

int main()
{
	deque<char> dq_front; //앞에서부터 받는 덱
	deque<char> dq_back; //뒤에서부터 받는 덱
	
	string a, t;
	cin >> a >> t;

	int front_index, last_index;//앞에서 부터 시작하는 index와 뒤에서 부터 시작하는 index;
	front_index = 0; last_index = t.size() - 1; //index의 위치 맨 처음과 맨 끝으로 조정

	while (front_index <= last_index) //반복문 수행
	{
		while (front_index <= last_index) //앞에서부터 시작
		{
			bool b = false;
			dq_front.push_back(t[front_index]); //문자 덱에 삽입
			front_index++; //인덱스 위치 옮기기
			if (dq_front.size() >= a.size()) //A의 크기만큼의 문자가 덱에 있다면
			{
				b = true;
				for (int i = 0; i < a.size(); i++) { //A와 일치하지 않다면 b = false, break;
					if (a[i] != dq_front[dq_front.size() - a.size() + i]) {
						b = false;
						break;
					}
				}
			}
			if (b) { //만약 A와 일치한다면 A의 크기만큼 덱에서 제거
				for (int i = 0; i < a.size(); i++) dq_front.pop_back();
				break;
			}
		}
		while (front_index <= last_index) //뒤의 문자 부터 시작
		{
			dq_back.push_front(t[last_index]);
			last_index--;
			bool b = false;
			if (dq_back.size() >= a.size())
			{
				b = true;
				for (int i = 0; i < a.size(); i++) {
					if (a[i] != dq_back[i]) {
						b = false;
						break;
					}
				}
			}
			if (b) {
				for (int i = 0; i < a.size(); i++)
					dq_back.pop_front();
				break;
			}
		}
	}
	string answer;
	for (int i = 0; i < dq_front.size(); i++) answer.push_back(dq_front[i]);
	for (int i = 0; i < dq_back.size(); i++) answer.push_back(dq_back[i]); //string answer로 모두 합친 후
	while(answer.find(a) < 30000) //여전히 A와 같은것이 남아있다면 제거
		answer.erase(answer.find(a), a.size());
	if (!answer.empty()) cout << answer << '\n'; //출력
	
}