[알고리즘/파이썬] 백준 2607번 - 비슷한 단어

 

 

 

 

 

2607번: 비슷한 단어

 

문제 이해하는데 한참 걸렸다. 책좀 더 읽어야겠다.

 

아래 코드처럼 모든경우의 수를 다 확인하는 방법으로 풀었다.

 

입력은 대문자만 된다고 했으니 대문자 32개를 입력받을수 있도록 했다. ( length가 32인 list에 0으로 초기화 ) 

 

대문자는 아스키코드 65부터 시작하니까 입력받은 문자를 65로 나눈 나머지가 0이면 A, 나머지가 1이면 B 이런식으로 처리했다. 

 

 그후 구성이 같은지, 문자를 하나 뺐을때 같은지, 문자를 하나 더했을때 같은지, 기존 문자 하나를 다른 문자로 바꿨을때 같은지 확인하면 된다. 이중 하나라도 걸리면 비슷한 문자다.

 

n = int(input())
words= []

for _ in range(n):
    word = input()
    words.append(word)

first_word = [0 for i in range(32)]

ans = 0
for i in range(len(words)):
    word = [0 for j in range(32)]

    # 첫번째 단어
    if i ==0 :
        for c in words[i]:
            first_word[ord(c)%65] += 1
    # 두번째 단어
    else:
        for c in words[i]:
            word[ord(c)%65] += 1

    # 같은구성
    if ''.join(str(word)) == ''.join(str(first_word)):
        ans +=1
        continue;

    # 기존 문자를 빼는경우
    for j in range(32):
        if word[j] >=1:
            word[j] -= 1
            if ''.join(str(word)) == ''.join(str(first_word)):
                ans +=1
                continue
            word[j] +=1

    # 새로운 문자 하나를 추가 하는 경우
    for j in range(32):
        word[j] += 1
        if ''.join(str(word)) == ''.join(str(first_word)):
            ans +=1
            continue
        word[j] -=1

    # 기존 문자 하나를 바꾸는 경우
    for j in range(32):
        if word[j] >= 1:
            # 기존문자 하나 제거
            word[j] -= 1
            # 다른문자로 대체
            for k in range(32):
                if k != j:
                    word[k] +=1
                    if ''.join(str(word)) == ''.join(str(first_word)):
                        ans +=1
                        continue
                    word[k] -=1
            word[j] +=1

print(ans)