[백준] 15829: Hashing

GitHub: https://github.com/tyt0815

tyt0815 - Overview

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

15829번: Hashing

Hashing

내용자체는 학교에서 배웠던 자료구조 문제입니다. 어려운 점은 없지만 입력과 출력의 조건에 함정(?)이 있습니다.

주어진 해쉬 함수는 단순한데 여기서 문제는 r이 26이고 i제곱으로 증가하기 때문에 폭발적으로 증가한다는 점 입니다. 그래서 문제 채점이 Small과 Large 두문제로 나뉘어 있는데, 단순하게 해쉬함수를 구현하면 Small은 통과하고 Large는 통과할 수 없습니다. Large문제에서 문자열의 최대 길이는 50으로 26의 50제곱은  10의 70제곱의 수로 평범한 자료형으로 표현 할 수 없습니다. (usigned long long < 2의 64제곱 = 18,446,744,073,709,551,616) 따라서 계산하는 틈틈이 mod M으로 수를 줄여주어야 한다는 것입니다. 여기서 중간중간에 mod 연산을 하더라도 결과값이 변하지 않는다는 것은 직접 계산해 보시면 알 수 있습니다.

#include <iostream>
#include <math.h>
#define R 31
#define M 1234567891

using namespace std;

int main()
{
    uint64_t n, hashValue = 0, ri = 1;
    char c;
    cin >> n;
    for(uint64_t i = 0; i < n; ++i)
    {
        cin >> c;
        hashValue = (hashValue + (c-'a'+1)*ri)%M;
        ri = (ri*R)%M;
    }
    
    cout << hashValue;

    return 0;
}

 구현자체는 어렵지는 않지만(solved 기준 브론즈2) 입력과 출력에 대한 조건을 다시 생각해 보고 기초를 다시 리마인드하는 경험이 되었습니다.