[C++] 백준 15829 : Hashing

그냥 아무 생각 없이 시키는대로 풀었을 때 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 시켜주어야한다.