[백준] 15829번: Hashing [C++]

 

알고리즘 분류: 구현, 문자열, 해싱

문제 링크: https://www.acmicpc.net/problem/15829

15829번: Hashing

 

 

【 풀이 】

 

문자열을 입력받아 해시값을 계산하는 문제이다.

이 문제는 한마디로, 문자열 각 인덱스의 문자값에 고유 계수를 거듭제곱한 값을 곱하여 그 수들을 더한 해시값을 구하라는 것이다.

그러기 위해서 먼저 m을 1234567891로, 각 계수에 곱할 r을 1로 선언한다.

그러고 아스키 코드 값을 이용해 문자열 각 인덱스의 값을 구하여 계산하면 되는 간단한 문제이다.

 

다만, 100점을 받기 위해서는 각 자료형에 더욱 신경써주어야 한다.

m이 있는 이유는 자료형의 범위를 넘어가는 값을 다시 초기화시켜주기 위함이다.

따라서 각 계산값들이 자료형의 범위를 넘어가지 않도록 계산마다 m으로 나눈 나머지를 구하게끔 하면 된다.

 

 

 

【 코드 】

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

string s;
int main(void)
{
	int l;
	long long m = 1234567891;
	long long r = 1;
	long long sum = 0;
	cin >> l;
	cin >> s;
	for (int i = 0; i < l; i++)
	{
		sum += ((long(s[i]) - 96) * r)%m;
		r = (r*31)%m;
	}
	cout << sum % m;
}