[개쉬운 풀이] 백준 2607 비슷한 단어

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

문제

영문 알파벳 대문자로 이루어진 두 단어가 다음의 두 가지 조건을 만족하면 같은 구성을 갖는다고 말한다.

두 개의 단어가 같은 종류의 문자로 이루어져 있다.
같은 문자는 같은 개수 만큼 있다.
예를 들어 "DOG"와 "GOD"은 둘 다 'D', 'G', 'O' 세 종류의 문자로 이루어져 있으며 양쪽 모두 'D', 'G', 'O' 가 하나씩 있으므로 이 둘은 같은 구성을 갖는다. 하지만 "GOD"과 "GOOD"의 경우 "GOD"에는 'O'가 하나, "GOOD"에는 'O'가 두 개 있으므로 이 둘은 다른 구성을 갖는다.

두 단어가 같은 구성을 갖는 경우, 또는 한 단어에서 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우에 이들 두 단어를 서로 비슷한 단어라고 한다.

예를 들어 "DOG"와 "GOD"은 같은 구성을 가지므로 이 둘은 비슷한 단어이다. 또한 "GOD"에서 'O'를 하나 추가하면 "GOOD" 과 같은 구성을 갖게 되므로 이 둘 또한 비슷한 단어이다. 하지만 "DOG"에서 하나의 문자를 더하거나, 빼거나, 바꾸어도 "DOLL"과 같은 구성이 되지는 않으므로 "DOG"과 "DOLL"은 비슷한 단어가 아니다.

입력으로 여러 개의 서로 다른 단어가 주어질 때, 첫 번째 단어와 비슷한 단어가 모두 몇 개인지 찾아 출력하는 프로그램을 작성하시오.

생각 & 풀이

1. 주어진 조건에 맞게 문자열을 비교하면 좋을 것 같다.
2. 한 문자를 더하는 경우.
3. 한 문자를 빼는 경우.
4. 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우
5. 순서만 바꾸면 되는 경우.
6. map을 통해서 단어의 알파벳을 갯수를 저장한다.
7. 이를 비교할 단어의 알파벳 단위로 하나씩 제거하며 최종적으로 비교되는 단어의 알파벳과 map안의 알파벳 갯수를 비교한다.
   • targetSize = 비교대상 단어의 남은 알파벳 수
   • remainAlpha = 비교하는 단어의 남은 알파벳 수
8. vector에 해당하는 단어들을 담아서 출력한다.

코드

#include <iostream>
#include <vector>
#include <map>
#include <string>
#define endl '\n'
using namespace std;

int n;
vector<string> v;
int answer = 0;

void input(){
    cin >> n;
    v = vector<string> (n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
}

/*
비슷한 단어인 경우
1. 한 문자를 더하거나
2. 한 문자를 빼거나
3. 하나의 문자를 다른 문자로 바꾸어
4. 순서만 바꾸면 되는 경우

map을 이용해서 해결하자
*/

//string을 알파벳 단위로 분류하기
map<char,int> process(string tmp){
    map<char,int> m;
    for(char c : tmp){
        m[c] += 1;
    }
    return m;
}

// true : 비슷한 단어 , false : 비슷하지 않은 단어
bool compareFunction(string target, map<char,int> tmp){
    int minusPoint = 0;
    int targetSize = target.length(); 
    for(int i = 0; i < target.length(); i++){
        char c = target[i];
        
        //알파벳이 없는경우
        if(tmp.find(c) == tmp.end()){
            minusPoint += 1;
            //문자가 두개 이상 없으면 안되므로
            if(minusPoint > 1){
                return false;
            }
        }
        //알파벳이 있는 경우
        else{
            targetSize -= 1;
            tmp[c] -= 1;
            if(tmp[c] == 0) tmp.erase(c);
        }
    }
    int remainAlpha = 0;
    for(auto iter = tmp.begin(); iter != tmp.end(); iter++){
        remainAlpha += iter->second;
    }
    //문자 하나만 더하면 되는 경우
    if(targetSize == 0 && remainAlpha == 1) return true;
    //문자 하나만 빼면 되는 경우
    else if(targetSize == 1 && remainAlpha == 0) return true;
    //문자 하나만 바꾸면  되는 경우
    else if(targetSize == 1 && remainAlpha == 1) return true;
    //순서만 바꾸면 되는 경우
    else if(targetSize == 0 && remainAlpha == 0) return true;
    else return false;
}

void sol(){
    int answer = 0;
    string target = v[0];
    for(int i = 1; i < n; i++){
        map<char,int> tmp = process(v[i]);
        //비슷한 단어인지 판단하여 맞으면 answer + 1
        if(compareFunction(target, tmp)){
            answer += 1;
        }
    }

    cout << answer << endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    input();
    sol();

    return 0;
}

 

 

비슷한 단어로 판단하는 경우를 세분화하고 이를 구현하면 된다.

단어에서 알파벳을 이용하는 문제는 <map>을 이용하는 것이 좋아보인다.