[BOJ 10453] 문자열 변환

- 문제 요약

 

1. ab는 좋은 문자열이다.
2. 만약 문자열 [S]가 좋은 문자열이라면, 오른쪽과 왼쪽 끝에 각각 a와 b를 추가한 문자열 a[S]b 또한 좋은 문자열이다.
3. 만약 문자열 [S]와 [T]가 좋은 문자열이라면 이들을 붙여 쓴 [S][T] 또한 좋은 문자열이다.

첫 줄에 테스트 케이스의 수 T가 주어진다.
각각의 테스트 케이스마다, 한 줄에 문자열 A, B가 공백으로 분리되어 주어진다. (2<=(문자열 길이)<=100,000)

문자열 A를 '인접한 두 문자를 서로 바꾸는' 연산을 통해 문자열 B로 바꾸려고 한다. 이때 필요한 연산의 최소 횟수를 구하는 프로그램을 작성하시오. A를 B로 바꾸는 중에 나타나는 문자열도 모두 좋은 문자열이어야 한다.

 

 

- 알고리즘 정리

 

문자열 A에서 인접한 두 문자를 서로 바꾸는 연산을 통해 문자열 B로 바꿀 수 있다는 것은, 문자열에 사용되는 문자의 종류와 수가 같다는 뜻입니다. 그러므로 이를 이용하여 각 문자열에서 문자의 개수와 위치를 찾고, 위치의 차이를 결괏값에 더해주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

int t,l1,l2,result,i1,i2;
string a,b;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>t;
	while(t--){
		cin>>a>>b;
		l1=a.size();
		l2=b.size();
		if(l1!=l2){
			cout<<-1<<endl;
			continue;
		}
		result=i1=i2=0;
		while(true){
			while(i1<l1 && a[i1]=='a'){
				i1++;
			}
			while(i2<l2 && b[i2]=='a'){
				i2++;
			}
			if(i1>=l1 || i2>=l2){
				break;
			}
			result+=abs(i1++ - i2++);
		}
		cout<<result<<endl;
	}
}

코드 제출 결과