백준 2607번 [비슷한 단어](C++) -yes6686- 티스토리

백준 문제 풀이: 2607 [비슷한 단어]

---

문제 링크: https://www.acmicpc.net/problem/2607

문제 설명:

첫 번째 단어를 기준으로, 주어진 나머지 단어들이 비슷한 단어인지 판별하는 문제입니다.

두 단어가 비슷한 단어가 되는 조건은 다음과 같습니다:

• 한 문자를 더하거나, 삭제하거나, 바꾸어서 같은 구성을 만들 수 있는 경우

---

문제 해결 코드

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;

int alpha1[27]; // 기준 단어의 알파벳 개수
int alpha2[27]; // 비교 단어의 알파벳 개수

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    string str;
    cin >> str;

    // 기준 단어의 알파벳 개수 저장
    for (int i = 0; i < str.size(); i++) {
        alpha1[str[i] - 'A']++;
    }

    int ans = 0;

    // 나머지 단어들을 비교
    for (int i = 0; i < n - 1; i++) {
        string s;
        cin >> s;

        // 비교 단어의 알파벳 개수 저장
        for (int i = 0; i < s.size(); i++) {
            alpha2[s[i] - 'A']++;
        }

        int check = 1;
        int cnt1 = 0, cnt2 = 0;

        for (int i = 0; i < 26; i++) {
            // 두 단어 간 알파벳 차이가 2 이상이면 비슷한 단어가 아님
            if (abs(alpha1[i] - alpha2[i]) >= 2) {
                check = 0;
                break;
            }
            if (alpha1[i] > alpha2[i]) {
                cnt1++;
            } else if (alpha1[i] < alpha2[i]) {
                cnt2++;
            }
            if (cnt1 >= 2 || cnt2 >= 2) { // 변경이 두 번 이상 필요하면 비슷한 단어가 아님
                check = 0;
                break;
            }
        }

        if (check == 1) {
            ans++;
        }

        memset(alpha2, 0, sizeof(alpha2)); // 비교 단어의 알파벳 배열 초기화
    }

    cout << ans << '\n'; // 비슷한 단어 개수 출력
}

예제 입력:

4
DOG
GOD
GOOD
DOLL

예제 출력:

2

---

코드 설명

• 핵심 알고리즘: 두 단어의 알파벳 빈도수를 비교하여 비슷한 단어인지 판별
• 구현 세부사항:
  • 기준 단어의 알파벳 개수를 저장
  • 각 단어를 하나씩 비교하여 알파벳 개수 차이를 확인
  • 한 글자 추가/삭제/변경을 통해 같은 구성이 가능하면 비슷한 단어로 판별
• 시간 복잡도: O(N × 26), 각 단어를 비교하는 과정에서 26개의 알파벳을 체크

---

결과

주어진 단어 목록에서 기준 단어와 비슷한 단어의 개수를 정확히 계산합니다. 문자열과 해시(알파벳 개수 배열)를 활용한 문제 해결을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!