[백준] 15829번 Hashing(Python - 파이썬)

백준 15829번 문제입니다. (solved.ac)기준 브론즈 2 문제입니다.

문제 접근

문제의 내용은 해시 함수의 개념은 설명하느라 굉장히 길지만 문제 자체는 아주 쉽게 풀 수 있습니다. 

우선 알파벳에 고유한 번호를 부여한다고했는데 a를 1로 b를 2로 ... z를 26으로 부여한다고 합니다.

아스키코드상에서 a는 97 b는 98 ... z는 122이므로 아스키코드로 변환 후 - 96을 해주면 문제에서 원하는 고유한 번호가 됩니다.

문제에서 요구하는 해시 함수의 식은 힌트를 보면 아주 쉽게 도출해 낼 수 있습니다. 거듭제곱을 하는 r의 값이 31이기 때문에

예제 1을 해시 함수에 넣었을 때 나오는 식인 1 × 310 + 2 × 311 + 3 × 312 + 4 × 313 + 5 × 314 을 보면

str = "abcde"
for i in range(1, 5):
     cur = ord(str[i]) - 96
     hash += cur * 31 ** i

위와 같은 식을 도출해 낼 수 있습니다.

문제의 조건을 보면 Small (50점) 1 <= l <= 5 , Large(100점) 1 <= l <= 50 (100점)이 있습니다.

 해시함수를 설명하는 부분에서 나왔듯이 해시 충돌을 적게 일어나게 하기 위해 1234567891로 나누어 줘야 한다고 나와있는데 이 부분을 반영해주지 않는다면 50점 반영해준다면 100점이 나오게 되는 것 같습니다.

시그마 식에 mod M이라는 부분이 있는데 mod는 나머지 연산이라는 뜻의 modulo의 약자입니다.

 예를 들어 a mod b라고 한다면 a를 b로 나누었을 때의 나머지를 뜻하는데 a 보다 b가 더 크다면 a가 나머지가 됩니다. 

이 mod는 파이썬에서 %를 사용하여 쉽게 나타낼 수 있습니다.

 

정답 코드 

l = int(input())
str = input()
mod = 1234567891
hash = 0
# 아스키 코드에서 96을 빼주면 됨

for i in range(l):
     cur = ord(str[i]) - 96
     hash += cur * 31 ** i

print(hash % mod)