[백준 2607 / Python / 실버2] 비슷한 단어

문제

 

구현, 문자열 문제이다. 비슷한 단어가 될 수 있는 조건을 정확히 찾으면 쉬운 문제인데, 조건 하나를 빠뜨려서 조금 헤맸다.

 

from collections import defaultdict

import sys

input = sys.stdin.readline

"""

길이가 2이상 차이나면 제외.

1. 길이가 1차이나는 경우, 나머지 문자의 개수가 전부 같다면 비슷한 단어이다.

2. 길이가 같은 경우, 모든 문자가 같으면 비슷한 단어이다.

3. 길이가 같은 경우, 하나의 문자가 다르다면 비슷한 단어이다.

-> 이 3가지 외에 만족하는 케이스는 없다.

"""

N = int(input())

ref = input().strip()

ref_count = defaultdict(int)

for key in ref:

    ref_count[key] += 1

result = 0

for _ in range(N - 1):

    word = input().strip()

    diff_len = abs(len(ref) - len(word))

    if diff_len >= 2:

        continue

    word_count = defaultdict(int)

    for key in word:

        word_count[key] += 1

   

    # 모든 문자를 모은 합집합

    all_chars = set(ref) | set(word)

    diff_count = 0

    for char in all_chars:

        diff_count += abs(ref_count.get(char, 0) - word_count.get(char, 0))

        if diff_count > 2:

            break

    else:

        if diff_count == 0:  # 같은 구성

            result += 1

        elif diff_count == 1:  # 같은 구성에 단어 하나만 추가된 것

            result += 1

        elif diff_count == 2 and diff_len == 0:  # 길이와 나머지 구성이 같은데 단어 하나만 다른 것

            result += 1

print(result)

 

1. 우선 기준이 될 단어 ref 의 각 문자 당 개수를 세 둔다.

2. 비교대상 단어 word를 입력받는데, 만약 ref와 word의 len 차이가 2 이상이라면 절대 비슷한 단어가 될 수 없으니 넘어간다.

3. 비교대상 단어 word 의 각 문자 당 개수도 세 둔다.

4. ref와 word에 존재하는 모든 문자를 검사하기 위해, 순회용 문자의 합집합 all_chars를 만들어 둔다.

5. 이제 all_chars를 순회하면서 각 문자의 개수 차이를 세서 diff_count에 전부 더한다.

 

이 때 diff_count가 3 이상이면, 절대로 비슷한 단어가 될 수 없다. 그렇다면 남은 경우의 수는 diff_count가 0, 1, 2일 때이다.

 

diff_count가 0인 경우: 같은 구성 ( 'ABC', 'CBA' )

diff_count가 1인 경우: 같은 구성인데, 단어 하나가 추가된것 ( 'ABC', 'ABCD' )

diff_count가 2인 경우: 길이와 구성이 같은데, 단어 하나만 다른 것 ( 'ABC', 'ABG' )

-> 이 경우 왜 diff_count가 2냐면, C를 word에서 찾고 G를 ref에서 찾기 때문에 단어 한개가 다른데도 diff_count는 2가 추가된다.

 

이 외에 비슷한 단어가 되는 경우는 없다. 난 diff_count가 2인 경우도 정답이 될 수 있다는 걸 간과해서 좀 헤맸다.

 

결과