[알고리즘][Python] 백준(BOJ) 2607 비슷한 단어_파이썬

 

2607 비슷한 단어    www.acmicpc.net/problem/2607

2607번: 비슷한 단어

 

 

 

문제 풀기 전 공부할 것 : 구현, 브루트포스 알고리즘

 

 

 

 

 

 

 

풀이 1

<내용>

• 첫 번째 단어를 dictionary 형태로 word에 저장한다.
• 단어들을 반복하여 단어의 알파벳을 word에서 -1 한다.
• 한 문자를 더하거나 빼거나 다른 문자로 바꾸는 경우에만 res에 +1을 한다.

 

 

<코드>

import copy
import sys
input = sys.stdin.readline

n = int(input())
words = [input().rstrip() for _ in range(n)]
word = {}
for w in words[0]:
    if w in word:
        word[w] += 1
    else:
        word[w] = 1
        
res = 0
for i in range(1, n):
    if len(words[i]) > len(words[0])+1 or len(words[i]) < len(words[0])-1:
        continue
        
    check = copy.deepcopy(word)
    for w in words[i]:
        if w in check:
            check[w] -= 1
        else:
            check[w] = -1
    
    change = [0, 0]
    flag = True
    for c in check:
        if check[c] == 0:
            continue
        if check[c] == 1:
            change[1] += 1
        elif check[c] == -1:
            change[0] += 1
        else:
            flag = False
            break
    if sum(change) > 2:
        flag = False
    elif change[0] > 2 or change[1] > 2:
        flag = False
        
    if flag:
        res += 1
print(res)

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 위의 과정과 같으나 dictionary가 아닌 list로 표현해서 같은 방법으로 해결한다.

 

<코드>

import sys
input = sys.stdin.readline

n = int(input())
words = [[0 for _ in range(26)] for _ in range(n)]
for i in range(n):
    string = input().rstrip()
    for s in string:
        words[i][ord(s)-ord('A')] += 1
        
res = 0
for word in words[1:]:
    plus, minus = 0, 0
    for i in range(26):
        if word[i] > words[0][i]:
            plus += (word[i]-words[0][i])
        else:
            minus += (words[0][i]-word[i])
            
    if plus < 2 and minus < 2:
        res += 1
        
print(res)