백준 2607 비슷한 단어 Python

🐸 문제 정보

2607번: 비슷한 단어

 

🤖 알고리즘

구현

 

⏱️ 풀이 시간

34.18m

 

📝 풀이

단순한(?) 구현 문제였다.

일단 모든 문자를 딕셔너리로 처리하며, 단어 안에 해당 문자의 개수를 저장했다.

그리고 첫 번째 단어, 즉 기준이 되는 단어의 길이를 확인하여 기준 점수로 저장했다.

이후 과정은 아래와 같다.

1. 두 번째 단어부터 반복을 돈다. (이 때 임시 점수 변수를 선언한다)
2. 기준이 되는 단어와 같은 단어는 +1, 없거나 다른 단어는 -1을 해준다.
3. 기준 점수와 임시 점수를 비교해서, -1까지만 허용한다. (추가하거나 빼서 같은 구성이 되는 경우)
4. 길이가 같은 단어의 경우에는 문자 하나를 변경해서 같아지는 경우도 있을테니 -2까지 허용한다. (문자 하나를 변경해서 같은 구성이 되는 경우)

딕셔너리에서 값을 읽을 때는 get 메서드를 이용해서 읽어야 안전하다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
words = []
res = 0

for i in range(n):
    temp = {}
    for le in list(input().rstrip()):
        temp[le] = temp.get(le, 0) + 1
    words.append(temp)

st = sum(words[0][key] for key in words[0]) # 기준 - 1 까지 허용

for i in range(1, n):
    score = 0
    length = sum(words[i][key] for key in words[i])
    for key in words[i]:
        if words[i][key] == words[0].get(key, 0):
            score += words[i][key]
        elif key in words[0]:
            score += words[0][key]
            score -= abs(words[i][key] - words[0].get(key, 0))
        else:
            score -= abs(words[i][key] - words[0].get(key, 0))
    if length == st: # 길이 같은 경우에는 -2까지 허용
        if st - 2 <= score <= st: res += 1
    else:
        if st - 1 <= score <= st: res += 1

print(res)