[브론즈 2] 백준 15829 - Hashing (파이썬)

https://www.acmicpc.net/problem/15829

풀이

문자열에 대해 특정한 방식으로 해시 값을 계산하는 문제이다.

각 문자의 알파벳 순서에 가중치를 곱해서 더하는 방식이 사용된다.

mod = 1234567891        # 모듈러 값
po = [0] * L            # 거듭제곱 저장 리스트
po[0] = 1               # r^0 = 1

# r^1, r^2, ..., r^(L-1) 을 미리 계산
for i in range(1, L):
    po[i] = po[i - 1] * 31 % mod

문자열 길이가 최대 50이라 효울적으로 r ^ i % mod 값을 미리 계산해둔다.

H = 0
for i in range(L):
    H += (ord(S[i]) - ord('a') + 1) * po[i] % mod
    H %= mod

ord(S[i]) - ord(’a’) + 1을 통해서 문자의 알파벳 순서를 숫자로 변환한다.

각 문자마다 가중치를 곱해서 더하고 각 연산마다 mod를 취해서 오버플로우를 방지한다.

코드

# 백준 15829 - Hashing
# 분류 : 해쉬

L = int(input())
S = input()

mod = 1234567891
po = [0] * L
po[0] = 1
for i in range(1, L) :
    po[i] = po[i - 1] * 31 % mod

H = 0
for i in range(L) :
    H += (ord(S[i]) - ord('a') + 1) * po[i] % mod
    H %= mod

print(H)