백준 15829번 Hashing

 

Hashing은 문제에서 정의한 hash 함수 공식을 구현하는 문제이다. 공식은 아래와 같다.

여기서 r = 31,  M = 1234567891로 주어져있다.

입력은 첫번째 줄에서 문자열의 길이가 입력되고, 두번째 줄에서 문자열이 입력된다. 주어진 문자열은 소문자로만 구성되어 있다.출력은 해당 해시 함수를 적용한 정수 결과값을 출력하면 된다. 

# 문제에서 주어진 r과 M 정의
r = 31
M = 1234567891

length = int(input())
str = input()

sum = 0
for i in range(length):
    k = (ord(str[i])-96) * (r**i) # 문자를 숫자로 변환하여 자릿수에 맞는 r의 거듭제곱을 곱해줌
    sum += k # 연산한 값을 모두 더함
hash = sum%M # 총합을 모듈러 연산을 해 hash 값을 얻음

print(hash)