[백준] C++ 12904번(A와 B)

 

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
	string c1;
	string c2;
	
	cin>>c1>>c2;
	
	int num1=0;
	int num2=0;
	
	for(int i=0; i<c1.size(); i++)
	{
		if(c1[i]=='A')
		{
			num1++;
		}
		else if(c1[i]=='B')
		{
			num2++;
		}
	}
	
	int num3=0;
	int num4=0;
	
	for(int i=0; i<c2.size(); i++)
	{
		if(c2[i]=='A')
		{
			num3++;
		}
		else if(c2[i]=='B')
		{
			num4++;
		}
	}
	
	if(num1>num3||num2>num4)
	{
		cout<<0;
		return 0;
	}
	
	int A=num3-num1;
	int B=num4-num2;
	
	int start=0;
	int end=c2.size()-1;
	int dir=1;
	while(true)
	{
		if(c2[end]=='A')
		{
			A--;
			if(dir==1)
			{
				end--;
			}
			else
			{
				end++;
			}
			
		}
		else if(c2[end]=='B')
		{
			B--;
			int temp=start;
			
			start=end-dir;
			end=temp;
			dir=(dir*(-1));
		}
		
		
		if(A<0||B<0)
		{
			cout<<0;
			break;
		}
		else if(A==0&&B==0)
		{
			int sig=0;
			int dir=1;
			if(start>end)
			{
				dir=-1;	
			}

			for(int i=0; i<c1.size(); i++)
			{
				if(c2[start]!=c1[i])
				{
					sig=1;
					break;
				}
				start=start+dir;
			}
			if(sig==0)
			{
				cout<<1;	
			}
			else
			{
				cout<<0;
			}
			
			break;
		}
		
	}
	
	return 0;
}

첫 번째 입력하는 문자열을 S 두 번째 입력하는 문자을 T라고 두고 S가 T로 변환 가능한지 묻는 문제이다.

 

조건

1.A는 문자열 뒤에 추가

2.B는 문자열을 뒤집고 A를 추가(뒤집는다는 것은 AABB가 있으면 BBAA가 된다는 말이다.)

 

T-S해서 남는 갯수를 A와 B에 저장했다. 그리고 start, end, dir(방향)을 이용해서 T를 조금씩 줄여 S로 만들었다.

만약 B가 나오면 dir의 방향을 변경시켜준다.

 

A가 음수거나 B가 음수가 되면 false

A가 0이고 B가 0일 때 S와 T가 같은지 다시 검사해서 같으면 true