H. String Transformation

문제에서 well-formed라고 정의된 'a'와 'b'로만 구성된 문자열 A와 B가 주어진다. 두 인접한 문자를 바꾸면서 문자열 A를 문자열 B로 만드는 최소 회수를 구하는 문제다.

문자 'a' 를 '(' 로 바꾸고 문자 'b'를 ')'로 바꾸면 괄호 문자열이 되고 well-formed의 정의가 직관적이게 된다. 이 문제에서 문자열 A를 문자열 B로 바꿀 수 없는 경우는 두 문자열의 길이가 다른 경우 뿐이다. 문자 두 개로만 구성된 문자열이기 때문에 바꾸는 최소 회수 또한 직관적이게 생각할 수 있다.

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define MAXN 100005 int T, N, M; char A[MAXN], B[MAXN]; int main() { int i, j; for (scanf("%d", &T);T--;){ scanf("%s%s", A+1, B+1); N = strlen(A+1), M = strlen(B+1); if (N != M){ puts("-1"); continue; } int ans = 0; for (i=j=1;i<=N;i++) if (B[i] == 'a'){ while (A[j] != 'a') j++; ans += abs(i-j); j++; } printf("%d\n", ans); } }