[BOJ] 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"은 비슷한 단어가 아니다.

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

입력:

첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이하이다.

출력:

입력으로 주어진 첫 번째 단어와 비슷한 단어가 몇 개인지 첫째 줄에 출력한다.

풀이방법:

주어진 경우의 수가 많지 않기 때문에 모든 경우의 수에 대해 고려하도록 한다. main으로 선택한 단어는 비교할 단어가 들어올 때마다 복사해서 사용한다.

main 단어와 비교할 단어를 비교하면서 문자가 겹치는 것이 있는지 확인한다. 겹치는 문자가 있다면 remove를 하고 없다면 count를 증가시킨다. 모든 비교를 완료한 뒤에 count가 1 이하, 남은 단어가 1 이하인지 확인하도록 한다. 만약 각 값들이 2보다 크다면 '한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어' 조건에 해당하지 않게 된다.

N = int(input())
 
words = []
for _ in range(N):
    words.append(input())
 
main_word = words[0]
answer = 0
for word in words[1:]:
    target = list(main_word)
    count = 0
    for w in word:
        if w in target:
            target.remove(w)
        else:
            count+=1
 
    if count < 2 and len(target) < 2:
        answer+=1
 
print(answer)

문제링크:

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

2607번: 비슷한 단어