백준 10453 (C++) 문자열 변환

최초 업로드: 2025-11-12 01:44:50

최근 수정 시간: 2025-11-12 01:44:50

게시자: rlatjwls3333

카테고리: 백준

# [Gold V] 문자열 변환

[문제 링크](https://www.acmicpc.net/problem/10453)

## 문제 설명

좋은 문자열은 다음과 같이 정의된다.

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

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

예를 들어, A = aabbabab 이고 B = aaaabbbb라 해 보자. 그렇다면 다음과 같이 5번의 연산을 통해 A를 B로 변환할 수 있다.

aabbabab → aabbaabb → aabababb → aabaabbb → aaababbb → aaaabbbb

## 입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각각의 테스트 케이스마다, 한 줄에 문자열 A, B가 공백으로 분리되어 주어진다. 이때 A와 B는 좋은 문자열이며, 각각의 길이는 2 이상 100,000 이하이다.

## 출력

T줄에 걸쳐서, 각 테스트 케이스에서 주어진 문자열 A를 문자열 B로 변환할 때 필요한 연산의 수를 출력하시오.

만약 변환이 불가능한 경우 -1을 출력한다.

## 풀이
S의 a의 위치들을 차례대로 T의 a의 위치들에 배치하는 것이 가장 그리디합니다.

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--) {
        string a, b; cin >> a >> b;

long long cnt=0, idx=0;
 for(int i=0;i<a.length();i++) {
 while(idx<b.length() && b[idx]!='a') idx++;
 if(a[i]=='a') {
 cnt += abs(i-idx);
 idx++;
 }
 }
 cout << cnt << '\n';
 }
}
```