15829. Hashing

만약 해싱을 공부하고자 하면 이 문제를 필수적으로  풀어보길 바란다. 

해싱의 기본개념도 알 수 있고 간단한 구현도 가능하다.

구현의 경우, 문제를 그대로 구현하면 된다. 

여기서 31은 영어 최대 숫자인 26보다 큰 소수이기 때문에 설정하였다. (이 숫자는 소수를 사용하는 것이 좋을 것 같다.)

또한, 1234567891도 소수이다. 

 

#include<stdio.h>


int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	char buffer = 0;
	int number = 0;
	scanf("%d", &number);
	scanf("%c", &buffer);
	long long sum = 0;
	int box = 0;
	long long list[51] = { 0 };
	list[1] = 1;
	for (int i = 2; i < 51; i++) {
		list[i] = (list[i - 1] * 31) % 1234567891;
	}
	for(int i=1;i<=number;i++){
		scanf("%c", &buffer);
		box = buffer - 'a'+1;
		sum = (sum+box*list[i]) % 1234567891;
	}
	printf("%d", sum % 1234567891);
	return 0;
}

 

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

15829번: Hashing