백준 2607 - 비슷한 단어

 

 

문제 설명

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

1. 두 개의 단어가 같은 종류의 문자로 이루어져 있다.
2. 같은 문자는 같은 개수 만큼 있다.

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 문자열이 주어지고 첫번째 문자열과 비교하여 비슷한 구성을 갖는 문자열이 몇 개나 있는지 확인하는 문제이다.

비슷한 구성은 두 문자열을 이루는 철자가 모두 같거나, 하나의 문자를 수정하여 만들어 낼 수 있어야 한다.

수정에는 추가, 삭제, 변경이 있다.

 

해당 문제는 두 문자열을 비교하며 문자의 개수를 확인하면 풀 수 있다.

기준이 되는 문자열을 이루는 문자의 개수를 하나씩 세주고 비교할 문자열의 문자를 하나씩 살펴보며 같은 문자가 몇 개인지 확인한다.

 int same = 0;

 for (int i = 0; i < Other.str.length(); i++)
 {
     char spell = Other.str[i];
     if (temp[spell] > 0)
     {
         temp[spell]--;
         same++;
     }
 }

해당 과정이 완료되면, 두 문자열의 길이에 따라 비슷한 구성인지 판단하는 과정을 거친다.

 

만약, 두 문자열의 길이가 같다면 동일한 문자의 개수는 문자열의 길이와 같거나 하나가 작아도 된다.

동일한 문자의 개수가 하나 작은 경우에는 하나의 문자를 변경하면 되기 때문이다.

 

만약, 두 문자열의 길이가 1차이 난다면 더 작은 길이의 문자열과 동일한 문자의 개수가 같으면 동일한 구성이다.

기준이 되는 문자열이 짧다면 하나를 추가하여 비교하는 문자열을 만들 수 있고, 비교할 문자열이 더 짧다면 마찬가지로 하나를 더해 기준이 되는 문자열을 만들 수 있기 때문이다.

 

위와 같은 과정을 쉽게 적용하기 위해 구조체를 만들어 진행하면 깔끔하게 할 수 있다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N;

struct Word
{
    Word(string s) : str(s)
    {
        for (char spell = 'A'; spell <= 'Z'; spell++)
        {
            spellCount.insert({ spell, 0 });
        }

        for (auto c : str)
        {
            spellCount[c]++;
        }
    };

    string str;
    map<char, int> spellCount;

    bool operator==(const Word& Other)
    {
        int lengthDiff = abs((int)str.length() - (int)Other.str.length());
        if (lengthDiff > 1) return false;

        map<char, int> temp(spellCount);
        int same = 0;

        for (int i = 0; i < Other.str.length(); i++)
        {
            char spell = Other.str[i];
            if (temp[spell] > 0)
            {
                temp[spell]--;
                same++;
            }
        }

        if (lengthDiff == 0)
        {
            if (same == str.length() || same == str.length() - 1) return true;
        }
        else
        {
            int shortLength = min(str.length(), Other.str.length());
            if (same == shortLength) return true;
        }

        return false;
    }
};

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

    cin >> N;

    string str;
    cin >> str;

    Word first(str);

    int ans = 0;
    for (int i = 0; i < N - 1; i++)
    {
        string temp;
        cin >> temp;

        Word current(temp);

        if (first == current) ans++;
    }

    cout << ans++;

    return 0;
}

---