백준 2607 비슷한 단어 C++

백준 비슷한 단어 2607 C++

---

문제

문제

영문 대문자로 이루어진 여러 단어가 주어졌을 때, 첫 번째 단어와 “비슷한 단어”의 개수를 출력합니다. 여기서 “비슷한 단어”란 두 단어의 알파벳 빈도 구성이 완전히 같거나, 한 번의 연산(추가 1회 / 삭제 1회 / 치환 1회)으로 같아질 수 있는 경우를 의미합니다.

테스트케이스

예시 입력

4
DOG
GOD
GOOD
DOLL

예시 출력

2

설명: DOG와 GOD는 구성 동일, DOG와 GOOD은 ‘O’ 추가 1회로 동일, DOG와 DOLL은 한 번으로 맞출 수 없으므로 제외입니다.

문제 작동원리

알파벳 26개에 대한 빈도 배열을 사용하여, 첫 단어와 각 단어의 L1 거리(절댓값 합)를 계산합니다.

• sumCheck = \(\Sigma |check[j] - check2[j]|\)
• 길이 차이 k = \(|len1 - len2|\)

비슷한 단어인지의 최종 판정은 “추가/삭제/치환” 1회 허용에 정확히 대응하도록 다음과 같이 합니다.

• sumCheck == 0 → 구성 완전히 동일.
• sumCheck == 1 → 추가 또는 삭제 1회로 동일 가능(길이 차이 1).
• sumCheck == 2 그리고 길이 같음 → 치환 1회로 동일 가능.

이를 한 줄 조건으로 안전하게 쓰면 \(sumCheck \le 2\) && \(k \le 1\) 입니다. (길이 차이 2 이상이면 최소 2회 이상의 추가/삭제가 필요하므로 배제됩니다.)

---

아이디어

• 첫 단어의 알파벳 빈도를 check[26]에 저장합니다.
• 비교 대상 단어의 알파벳 빈도를 check2[26]에 저장합니다.
• 두 배열의 원소별 차이의 절댓값을 모두 더해 sumCheck를 얻습니다.
• 길이 차이 k도 구합니다.
• 판정식: if (sumCheck <= 2 && k <= 1) cnt++;
• sumCheck == 0 → 바로 포함.
• sumCheck == 1 → 추가/삭제 1회, 길이 차이 1이 자연스럽게 충족.
• sumCheck == 2 && k == 0 → 치환 1회.
• 나머지는 제외입니다.

---

전체코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(void)
{
    int N,cnt=0;
    int check[26]={0};
    cin>>N;
    char st1[11],st2[11];
    cin>>st1;
    for(int i=0;st1[i]!='\0';i++)
        check[st1[i]-'A']++;
    for(int i=1;i<N;i++)
    {
        int check2[26]={0};
        int sumCheck=0;
        cin>>st2;
        for(int j=0;st2[j]!='\0';j++)
            check2[st2[j]-'A']++;
        for(int j=0;j<26;j++)
        {
            sumCheck+=abs(check[j]-check2[j]);
        }
        int k=abs((int)(strlen(st1)-strlen(st2)));
        if(sumCheck<=2 && k<=1)
            cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

---

문제풀이

요청하신 대로 빈도 배열을 26칸 전부 시각화하여, 어떤 식으로 채워지고 어떤 조건에서 “비슷한 단어”로 판정되는지 생략 없이 보여드립니다.

• 배열 인덱스는 알파벳 순서 A(0) … Z(25)입니다.
• 표기는 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 순서의 정수 빈도로 적습니다.
• 또한 한 줄짜리 문자열 표기 000…도 같이 적습니다(알파벳 개수가 2 이상이면 해당 위치에 2, 3처럼 실제 개수를 그대로 표기).

기준 단어: `DOG`

• 문자: D=1, O=1, G=1
• check 배열 (숫자열)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

• check 배열 (문자열)

00010010000000010000000000

(설명: D 위치=1, G 위치=1, O 위치=1, 나머지 0입니다.)

---

비교 1: `GOD` (구성 동일 케이스)

• 문자: G=1, O=1, D=1
• check2 (숫자열)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

• check2 (문자열)

0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

• |check - check2| (숫자열)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

• sumCheck = 0
• 길이: len("DOG")=3, len("GOD")=3, k=0
• 판정: \(sumCheck \le 2\) 이고 \(k \le 1\) → 포함(구성 동일).

---

비교 2: `GOOD` (추가/삭제 1회 케이스)

• 문자: G=1, O=2, D=1
• check2 (숫자열)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 0 0 1 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0

• check2 (문자열)

0 0 0 1 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0

• |check - check2| (숫자열)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

(O에서만 1 차이)

• sumCheck = 1
• 길이: len("DOG")=3, len("GOOD")=4, k=1
• 판정: \(sumCheck \le 2\) 이고 \(k \le 1\) → 포함(추가 1회로 동일 가능).

---

비교 3: `DOLL` (배제 케이스)

• 문자: D=1, O=1, L=2
• check2 (숫자열)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 0 0 1 0 0 0 0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 0 0 0

• check2 (문자열)

0 0 0 1 0 0 0 0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 0 0 0

• |check - check2| (숫자열)

0 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0

(G에서 1 부족, L에서 2 초과)

• sumCheck = 1 + 2 = 3
• 길이: len("DOG")=3, len("DOLL")=4, k=1
• 판정: \(sumCheck \le 2\)가 아니므로 제외(한 번의 연산으로는 불가능).

---

비교 4: `DOT` (치환 1회 케이스 확인)

• 문자: D=1, O=1, T=1
• check2 (숫자열)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0

• check2 (문자열)

0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0

• |check - check2| (숫자열)

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0

(G 1 감소, T 1 증가 → 절댓값 합 2)

• sumCheck = 2
• 길이: len("DOG")=3, len("DOT")=3, k=0
• 판정: \(sumCheck \le 2\)이고 \(k \le 1\) → 포함(치환 1회).

---

추가 확인 5: `A` vs `AAA` 같은 잘못 포함 방지 예시

• 기준이 A, 비교가 AAA라고 가정하면
• sumCheck = 2, k = 2
• 우리 조건: \(sumCheck \le 2\)라도 \(k \le 1\)이 아니므로 제외됩니다.

이처럼 \(k \le 1\)을 함께 보아야 “한 번의 연산”만 허용한다는 문제 정의에 정확히 부합합니다.

---

결론

• 본 풀이는 알파벳 빈도 배열로 두 단어의 차이를 절댓값 합으로 계산하고, 길이 차이를 함께 고려하여 “추가/삭제/치환 1회 허용”이라는 조건을 정확히 반영합니다.
• 최종 판정식 \(sumCheck \le 2\) && \(k \le 1\)은
• 구성 동일(sumCheck=0),
• 추가/삭제 1회(sumCheck=1, 길이 차이 1),
• 치환 1회(sumCheck=2, 길이 차이 0)
• 를 모두 포함하고, 그 외는 배제하여 정답을 안정적으로 산출합니다.