알고리즘/백준[baekjoon]

[baekjoon] 백준 15829번 : Hashing (by python 파이썬)

코딩하는이씨 2022. 4. 7. 17:34
728x90
반응형

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

 

15829번: Hashing

APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정

www.acmicpc.net

 

정답 code

import sys
L = int(sys.stdin.readline())
s = sys.stdin.readline()
sum = 0
for i in range(L):
    sum += ((ord(s[i])-96)*(31**i))
print(sum  % 1234567891)

 

 

solution

 

이번문제에서 막혔던 부분은 문제가 장황한것이였는데 막상 식만 보면 풀 수 있었다.

 

 H=∑i=0 l−1 airi modM

 

해당 식을 뜯어보면 0부터 l-1까지 

a를 1로둔상태에서 b는 2 c는 3 ... z 는 26 이런식으로 잡고

r 값인 31의 i제곱을 해준 후

m 값인 1234567891로 나눈 나머지를 구하면 정답이 된다.

 

소문자 a의 아스키 코드값은 97임으로

입력받은 a를 ord()로 아스키 코드 값으로 바꾼후 -96해주면 된다.

 

728x90
반응형