[알고리즘][백준] 2607. 비슷한 단어

문제

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

 

문제 아이디어

사실 단어 개수는 100개, 길이는 10개라 완전 탐색이면 충분합니다.

리스트 하나를 돌면서 같은 단어가 있으면 하나씩 빼주고, 남는 것끼리만 비교해주면 됩니다.

예를 들어,

GOOOODF / GOCOOOAOOEOD

 

GOOOODF를 기준으로 탐색해줍니다.

0번째: G를 각각 빼줍니다 -> OOOODF / OOOOOOOD

1번째: O를 각각 빼줍니다. -> OOODF / COOOAOOEOD

... 각각 O, O, O, D가 있으므로 양쪽에서 빼줍니다. -> F / CAOOEO

 

이러면 각각 F와 CAOOEO가 있는데, F -> C 로 치환한다고 해도, 아직 AOOEO를 추가해야 같은 문자가 됩니다.

결국 CAOOEO와 F 중에서 더 긴 문자열의 길이가 1보다 작거나 같아야만 정답이 됩니다.

 

N = int(input())

wordMap = {}
word = list(input())
answer = 0

for idx in range(N - 1):
    nWord = list(input())
    tWord = word.copy()
    templist = []
    # 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어
    while tWord:
        w = tWord.pop()
        if w in nWord:
            nWord.remove(w)
        else:
            templist.append(w)

    if max(len(templist), len(nWord)) <= 1:
        answer += 1
        

print(answer)

list(str): 문자열을 캐릭터 리스트로 바꾸는 방법
list.remove(c): 문자열에서 문자 c를 제거하는 방법