'x'와 'y' 문자로만 구성되고 길이가 서로 같은 두 문자열 s1과 s2가 있다고 가정해 보겠습니다. 우리의 목표는 이 두 문자열을 완전히 동일하게 만드는 것입니다. 단, 문자 교환은 반드시 서로 다른 문자열에 속한 두 문자 사이에서만 허용됩니다. 즉, s1[i]와 s2[j]를 맞바꾸는 방식입니다. 두 문자열을 같게 만들기 위해 필요한 최소 스왑 횟수를 구하고, 불가능한 경우에는 -1을 반환해야 합니다.
예를 들어 s1 = "xy", s2 = "yx"라고 한다면 정답은 2입니다. 먼저 s1[0]과 s2[0]을 스왑하면 s1 = "yy", s2 = "xx"가 되고, 이어서 s1[0]과 s2[1]을 스왑하면 s1 = "xy", s2 = "xy"가 되어 두 문자열이 동일해지기 때문입니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- x1, x2, y1, y2를 모두 0으로 초기화합니다.
- i를 0부터 s1의 길이까지 순회하며 다음을 수행합니다.
- a = s1[i], b = s2[i]로 설정합니다.
- a와 b가 서로 다른 경우에만 아래를 수행합니다.
- a가 'x'이면 x1을, 그렇지 않으면 y1을 1 증가시킵니다.
- b가 'x'이면 x2를, 그렇지 않으면 y2를 1 증가시킵니다.
- (x1 + x2)가 홀수이거나 (y1 + y2)가 홀수이면 -1을 반환합니다. 어긋난 위치에서 'x'의 개수 합이 홀수라면 짝을 지어 스왑할 수 없기 때문입니다.
- x1/2 + y1/2 + (x1 mod 2) * 2를 반환합니다. 같은 유형의 어긋남("xy" vs "yx")끼리는 한 번의 스왑으로 두 위치가 동시에 해결되지만, 유형이 섞여 남은 쌍 하나는 두 번의 스왑이 필요하기 때문입니다.
C++ 구현 예제
아래 구현 코드를 살펴보며 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minimumSwap(string s1, string s2) {
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
for(int i = 0; i < s1.size(); i++){
char a = s1[i];
char b = s2[i];
if(a != b){
if(a == 'x')x1++;
else y1++;
if(b == 'x')x2++;
else y2++;
}
}
if ((x1 + x2) & 1 || (y1 + y2) & 1)return -1;
return x1/2 + y1/2 + (x1 % 2) * 2;
}
};
main(){
Solution ob;
cout <<ob.minimumSwap("xy", "yx");
}입력
"xy" "yx"
출력
2
알고리즘 동작 원리 정리
각 어긋난 위치에서는 항상 한쪽은 'x', 다른 쪽은 'y'이므로, x1은 s1에 'x'가 있는 어긋남의 개수, y1은 s1에 'y'가 있는 어긋남의 개수를 의미합니다. 같은 유형의 어긋남 두 개는 한 번의 스왑으로 동시에 해결되므로 각각 절반씩(x1/2, y1/2)이 필요하고, 홀수 개가 남아 유형이 섞인 경우에는 추가로 2번의 스왑((x1 % 2) * 2)이 필요합니다. 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.