[BOJ] 백준 15829 Hashing

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

15829번: Hashing

문제가 상당히 깁니다만 대부분 Hashing에 대한 개념을 짚고 있습니다.

요약

가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다.

보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들 테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!!)로 하자.

이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다.

 

Python 코드

stringLength = int(input())
str = input()
answer = 0
for i in range(stringLength):
    answer += (ord(str[i])-96)*(31**i)
print(answer % 1234567891)

ord 함수는 문자의 아스키 코드 값을 return 합니다.

a의 아스키 코드는 97인데 이 친구가 1이 되어야 하므로 96을 빼줍니다.

그리고 r의 i 제곱을 곱해주어야 합니다.

r은 31로 값이 주어졌고 파이썬에서 제곱 표시는 **로 표현합니다.

마지막으로 이렇게 계산된 값들을 전부 더해주어야 하죠.

수식을 보이는 그대로 코드로 표현했습니다.

차근차근히 따라가면 누구나 쉽게 풀 수 있다고 생각합니다.