Python3/백준 알고리즘
2022.02.24 [백준] (python 파이썬) Hashing
ian's coding
2022. 2. 24. 20:11
728x90
반응형
https://www.acmicpc.net/problem/15829
15829번: Hashing
APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정
www.acmicpc.net
풀이
우선 딕셔너리를 이용해 각 알파벳에 고유 번호를 지정해 주었다.
참고로 아스키 코드에서 문자로 변환은 chr(), 문자에서 아스키 코드로는 ord()를 사용하면 된다.
그리고 s의 길이만큼 for문을 돌려 각 (알파벳의 고유값*31**(알파벳의 인덱스))%m을 해주었다.
총 해쉬합인 sum을 그대로 출력했을 때, 50%성공이 결과로 나왔다. 아마 출력할 수 있는 범위를 벗어 난듯하다.
그래서 sum%m을 해주니 100%성공이 결과로 나왔다.
|
1
2
3
4
5
6
7
8
9
10
|
L=int(input())
s=input()
m=1234567891
dict={}
for i in range(1,27):
dict[chr(96+i)]=i
sum=0
for i in range(len(s)):
sum+=(dict[s[i]]*31**i)%m
print(sum%m)
|
cs |
728x90
반응형