그냥 아무 생각 없이 시키는대로 풀었을 때 50점이 나온 코드
#include <iostream>
#include <cmath>
using namespace std;
string str;
char c;
int main(){
int L;
long long hash = 0;
scanf("%d",&L);
cin >> str;
for(int i=0; i<str.size(); i++){
c = str[i];
hash += (c - 96) * pow(31, i);
}
printf("%lld\n", hash);
return 0;
}
알고보니 문자열의 길이가 50이 되면 숫자가 무지무지 커지기 때문에 오류가 발생하여 50점을 받은 것이다.
문자를 잘 읽도록 하자. 해시가 너무 길면 안되니까 소수인 큰 수 M으로 나눈다는 말이 힌트로 적혀있다.
해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자.
100점을 맞은 코드
#include <iostream>
#include <cmath>
using namespace std;
string str;
char a; // 주어진 문자
long long M = 1234567891; // 서로소 M
int main(){
int L;
long long hash = 0;
scanf("%d",&L);
cin >> str;
long long r = 1;
for(int i=0; i<L; i++){
a = str[i];
hash = (hash + (a - 96) * r) % M; // (a * r) mod M
r = (r * 31) % M; // pow(r, n); -> 값이 너무 커지니까 계속 mod M 해준다.
}
printf("%lld\n", hash);
return 0;
}
계속 해시값이 커지는 것을 방지하기 위해서 M으로 mod 시켜주어야한다.