[C] 백준 | 15829번 코드 - Hashing

> 문제

-생략- 어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다.

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

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

 

> 핵심

overflow가 생기지 않게 나머지 연산 하기.

long long 형 사용하기

 

>풀이과정

그냥 문제를 찬찬히 읽고 pow 함수를 사용해서 풀었는데 처음에 50점이 나왔다.

왜그런가 했더니 문자열 길이가 50까지이므로 31^50 승을 계산하면 수가 너무 커서 당연히 오류가 발생한다..

 

그래서 반복문으로 덧셈을 더하는 과정에서 틈틈히 소수 M으로 나누어주는 과정이 필요하다.

 

틈틈히 나눠주는데도 50점이 나오길래 열을 좀 받았는데,,

혹시나 해서 hash_value 의 자료형을 int형에서 long long 형으로 바꿔주니 바로 100점이 나오더라.. 허탈 :X

 

그래도 구글링 하면서 여러가지 또 배웠다.

 

1. 해시값은 소수로 나눴을 때 가장 효율적으로 사용할 수 있다.

2. 나머지 연산 방법

>> (a + b) mod n = {(a mod n) + (b mod n)} mod n

>> (a - b) mod n = {(a mod n) - (b mod n)} mod n

>> (a * b) mod n = {(a mod n) * (b mod n)} mod n

 

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define M 1234567891

int main()
{
	int len, i;
	long long hash_value = 0, R = 1;
	char str[51];

	scanf("%d %s", &len, str);

	for (i = 0; i < len; i++)
	{
		hash_value = (hash_value + (str[i] - 'a' + 1) * R) % M;
		R = (R * 31) % M;
	}
	printf("%lld\n", hash_value);

	return 0;
}