[자료구조/해시] 백준 15829 Hashing - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

15829번: Hashing

 

 

 

2. 문제 풀이

 주어진 해시함수에 따라 해시값을 구하는 문제입니다. 알파벳(a_i)은 a~z까지 1~26으로 나타내고, i번째 글자는 31의 i제곱을 곱해줍니다. M은 1234567891이며, M으로 나눈 나머지가 해시값이 됩니다.

 

 나머지 연산자는 결합법칙이 성립하므로, 각 문자의 해시값이 너무 커지지 않도록 미리미리 M으로 나머지를 구해주는 게 좋습니다. 

 

 

 

3. 코드

L = int(input()) #문자길이
string = input() #문자열

r = 31
M = 1234567891

sum = 0
cnt = 0
for s in string:
    i = ord(s)-96
    sum += (i * r**cnt) % M # 31의 제곱이 M을 넘어설 수 있으므로 매번 나눠줌
    cnt += 1

sum %= M # 합이 M을 넘어설 수 있으므로 다시 나눠줌
print(sum)

 해시함수의 정의대로 그대로 구현해줍니다. 파이썬에서는 ord( ) 함수를 사용해서 아스키코드 값을 얻을 수 있습니다.