백준 2607번 비슷한 단어 - C++ 풀이

---

 

1. 같은 구성을 갖는 경우, 모든 알파벳의 등장 횟수가 같다.
2. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, 한 알파벳만 등장 횟수가 1 차이 난다.
3. 한 문자를 다른 문자로 바꾸면 같은 구성을 갖는 경우, 두 알파벳의 등장 횟수가 각각 -1, 1 씩 차이 난다.

 

1. 같은 구성을 갖는 경우, 모든 알파벳의 등장 횟수가 같다.

 알파벳의 위치(순서)는 중요하지 않다. 각 알파벳의 등장 횟수만 같다면 같은 구성을 갖는다. 따라서 단어마다 각 알파벳의 등장 횟수를 세준다. A-Z까지 등장 횟수가 모두 일치한다면, 처음부터 같은 구성을 갖는 경우이다.

 

2. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, 한 알파벳만 등장 횟수가 1 차이 난다.

 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, 25개의 알파벳은 등장 횟수가 일치하고, 하나의 알파벳만 등장 횟수가 다르며, 그 차가 1 이어한다. 즉, 1개 적거나 많아야 한다.

 

3. 한 문자를 다른 문자로 바꾸면 같은 구성을 갖는 경우, 두 알파벳의 등장 횟수가 각각 -1, 1 씩 차이 난다.

 한 문자를 다른 문자로 바꾸면 같은 구성을 갖는 경우, 24개의 알파벳은 등장 횟수가 일치하고, 두 개의 알파벳만 등장 횟수가 다르며, 그 차가 각각 -1, 1 이어야 한다. 더 많은 것을 더 적은 것으로 바꾸어 구성을 맞춰주어야 하기 때문이다.

 

반응형

---

#include <iostream>
#include <vector>

using namespace std;

int N;
string S;
vector<int> s_alpha_cnt;

vector<int> countAlphabet(string s) {
    vector<int> ret(26, 0);
    
    for (auto c: s) {
        ret[c-'A']++;
    }
    
    return ret;
}

bool check(string word) {
    vector<int> word_alpha_cnt = countAlphabet(word);
    vector<int> diff;
    
    for (int i=0; i<26; i++) {
        if (word_alpha_cnt[i] != s_alpha_cnt[i]) {
            diff.push_back(word_alpha_cnt[i] - s_alpha_cnt[i]);
        }
    }
    
    // 같은 구성을 갖는 경우
    if (diff.empty()) return true;
    // 한 문자를 더하거나 빼는 경우
    if (diff.size() == 1 && abs(diff[0]) == 1) return true;
    // 하나의 문자를 다른 문자로 바꾸는 경우
    if (diff.size() == 2 && abs(diff[0]) == 1 && diff[0] + diff[1] == 0) return true;
    
    return false;
}

int solution() {
    int ret = 0;
    
    s_alpha_cnt = countAlphabet(S);
    
    for (int i=0; i<N-1; i++) {
        string temp;
        cin >> temp;
        
        if (check(temp)) ret++;
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    cin >> S;

    cout << solution();
    
    return 0;
}