Baekjoon 1411번 비슷한 단어

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

bool chk(string a, string b){
    if(a.size() != b.size()) return false;
    int n = a.size();
    map<char, char> m;
    vector<bool> alphabet(26, false);
    for(int i = 0; i < n; i++){
        char src = a[i];
        char dest = b[i];
        if(m.find(src) != m.end()){
            if(m[src] != dest){
                return false;
            }
        }
        else{
            if(alphabet[dest-'a']) return false;
            alphabet[dest-'a'] = true;
            for(int j = 0; j < n; j++){
                if(a[j] == src){
                    m[src] = dest;
                }
            }
        }
    }
    return true;
}

int main(){
    fastio;
    int n;
    cin >> n;
    vector<string> word(n);
    for(auto& i : word) cin >> i;
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(chk(word[i], word[j])) ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

단어 A 와 B 를 비교할 때 A 단어의 알파벳을 직접 교체해주다 보니 반례가 존재했다.

2
abca
cbxc

abca, cbxc
cbcc, cbxc
cbcc, cbxc
xbxx, cbxc