[파이썬] 15829번: Hashing

 

15829번: Hashing

 

처음엔 딕셔너리로 풀어서 제출했다가 다른 사람들의 코드가 유난히 짧은 것을 보고 의문이 생겨 찾아보니 아스키코드로 푸는 방법이 있는 것을 알았다. 

딕셔너리로 풀기

# Hashing - 딕셔너리로 풀기
m = 1234567891
r = 31

alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
num = {}

for i in range(len(alpha)):
    num[alpha[i]] = i + 1

L = int(input())
str = input()

def hash_mod(s):
    seq = 0
    for j in range(len(s)):
        seq += num[s[j]] * (r ** j)
    res = seq % m
    return res

print(hash_mod(str))

 

리스트에 알파벳을 하나씩 담아놓은 후 딕셔너리 'num'에 for 반복문을 이용하여 각 알파벳에 숫자를 마킹했다.

num = {'a':1, 'b':2 ·····} <- 이런 식으로 말이다.

새로운 함수 hash_mod를 만들어 문제에서 제시한 해시함수를 구현했다.

 

아스키코드로 풀기

# Hashing - 아스키코드 활용
L = int(input())
str = input()
res = 0

for i in range(L):
    res += (ord(str[i]) - 96) * (31 ** i)

res = res % 1234567891
print(res)

소문자 알파벳의 아스키코드는 'a' = 97부터 시작한다. 따라서 각 문자의 아스키코드에서 96씩을 빼주면 딕셔너리를 만들 필요없이 간단하게 알파벳을 숫자에 매핑할 수 있다. 

 

 

나는 수학 알러지가 있는 사람이라 문제가 너무 길거나 수학 기호가 등장하면 지레 겁먹는 편인데 막상 풀어보니 생각보다 그렇게 어렵지는 않았다. 해시 함수의 개념을 알고 있었기 때문인 것 같기도 하다. 해시를 배울 때에는 해시 함수를 직접 구현해볼 생각은 못했었는데 문제를 통해 간단하게나마 구현해볼 수 있어서 좋았다. 컴공 기초과목의 중요성을 다시금 느낄 수 있었던 문제이다.