[CF 1215C] Swap Letters

[CF 1215C] Swap Letters - 1500

문제 설명 : 

a와 b로만 이루어진 길이가 같은 두 문자열이 주어진다. 이 문자열에서 한 가지 연산을 할 수 있는데, 첫 번째 문자열에서 한 인덱스와 두 번째 문자열에서 한 인덱스를 골라서 서로 swap을 할 수가 있다. 이 연산을 최소한으로 사용하여 두 문자열을 같도록 만들어야 한다.

풀이 : 

두 문자열이 다를 수 있는 경우는 첫번째 문자열이 'a', 두번째 문자열이 'b'이거나 그 반대의 경우밖에 없다. 따라서 그 두가지 경우에 대해서 따로 저장을 해 놓는다. 문자열이 다르다는 것은 현재 문자와 다른 문자를 서로 swap해야 하므로 한번 swap을 했을 때, 총 다른 횟수는 2가 줄어들 것이다. 따라서 ab의 개수+ba의 개수가 짝수가 아니면 불가능하다. 만약 짝수라면 반드시 같게 만드는게 가능해지는데, ab에 저장된 인덱스를 ab[i] ,ab[i+1]인덱스를 swap해주면 된다. 이때 ab의 개수가 홀수라면 ab의 원소 한개를 같은 인덱스끼리 swap해서 ab값은 1 감소시키고, ba값을 1증가시켜주면 된다.

주의할 점 : 

vector에서 size()연산은 반환형이 unsigned int이기 때문에 for(int i=0 ; i<vector.size()-1 ; i++)을 쓰면 원래 한번도 안 돌아야하는데, unsigned로 저장되기 때문에 무한루프를 돌 수도 있다. 따라서 앞에 반드시 (int)로 명시적 형변환을 해주어야 한다.

배울 점 : 

문자열이 a,b로만 구성되어 있기 때문에 두 문자열이 다를 수 있는 경우는 오직 "ab"와 "ba"밖에 존재하지 않는다. 그래서 두 케이스에 대해서만 따로 저장을 해놓을 수가 있다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
#include<tuple>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
string exm;
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
template <typename T>
inline void showAll(vector<T> &v,string sep=""){
    for(T &here:v) cout<<here<<sep;}
template <typename T>
inline vector<int> int_seperation(T N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 200009;
 
char str[2][SIZE];
vector<int> ab,ba;
vector<pii> ans;
 
int main(){
    int n;  scanf("%d",&n);
 
    scanf("%s %s",str[0]+1,str[1]+1);
 
    for(int i=1 ; i<=n ; i++){
        if(str[0][i]=='a' && str[1][i]=='b'){
            ab.push_back(i);
        }
        if(str[0][i]=='b' && str[1][i]=='a'){
            ba.push_back(i);
        }
    }
 
    if(ab.size()&1){
        ans.push_back({ab.back(),ab.back()});
        ba.push_back(ab.back());
        ab.pop_back();
    }
 
    exm="-1";
    if(ba.size()&1){
        exf();
    }
 
    for(int i=0 ; i<(int)ab.size()-1 ; i+=2){
        ans.push_back({ab[i],ab[i+1]});
    }
 
    for(int i=0 ; i<(int)ba.size()-1 ; i+=2){
        ans.push_back({ba[i],ba[i+1]});
    }
 
    printf("%d\n",ans.size());
    for(auto &here:ans){
        printf("%d %d\n",here.first,here.second);
    }
 
    return 0;
}
/*

*/