boj 10453 문자열 변환

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

 

문제 키워드에 애드혹이 있던데 잘은 모르겠습니다.

제가 이 로직으로 접근하기 위해 생각한것 자체가 애드혹이 될 수는 있겠네요!

 

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

좋은 문자열의 정의가 이렇게 나옵니다.

그리고 입력으로 좋은 문자열 A, B가 주어지고, A -> B의 최소 연산 횟수를 구해야합니다.

 

우선 위 정의를 보고 알 수 있는건 "두 문자열의 구성은 같다" 입니다.

ab = S는 좋은 문자열이며, aSb도 좋은 문자열입니다. 그리고 SS도 좋은 문자열입니다.

여기서 사용된 a과 b의 갯수는 같습니다.

 

그렇다면 생각해볼 예외는 "두 문자열의 길이가 다른 경우" 입니다.

두 문자열의 길이가 다르다면 당연히 A -> B가 성립하지 않겠죠.

 

문제의 로직은

a, b의 갯수가 둘다 동일하기 때문에 b의 위치를 각각 찾습니다.

그리고 b 위치의 차이를 더합니다.

b의 갯수도 당연히 똑같기 때문에 하나라도 문자열의 길이를 벗어나면 종료할 수 있습니다.

 

 

#include <iostream>
using namespace std;
 
string x, y;
int len1, len2;
 
void func() {
    if (len1 != len2) {
        cout << "-1\m";
        return;
    }
 
    int ret = 0;
    int idx1 = 0;
    int idx2 = 0;
    while (1) {
        while (idx1 < len1 && x[idx1] == 'a') idx1++;
        while (idx2 < len2 && y[idx2] == 'a') idx2++;
        if (idx1 >= len1 || idx2 >= len2) break;
        ret += abs(idx1++ - idx2++);
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> x >> y;
    len1 = x.size();
    len2 = y.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}