[C++]백준15829 Hashing

03 Dec 2022 in Study on Algorithm

백준15829 Hashing 링크

문제

예제 입력

---

코드

#include<iostream>
using namespace std;
const int MOD = 1234567891;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int  L;
    long long r = 1, ans = 0;
    char c;
    cin >> L;
 
    for (int i = 0; i < L; i++) {
        cin >> c;
        ans = (ans + (c - 'a' + 1) * r) % MOD;
        r = (r * 31) % MOD;
    }
    cout << ans;
}

설명

기본적으로 C/C++의 기본 입출력함수를 혼합하여 사용되게 만들었지만 그만큼 실행속도에서 차이가 생기기 때문에 설정을 해주며 입력을 받고 해싱 함수의 기본 동작을 구현하기 위해서 문자를 값을 바꾸고 서로소인 두 소수 r, mod로 수열의 합을 반복문으로 계산해주는데 '모듈러 사칙연산 법칙'을 사용하여 구현합니다.

덧셈 : (A + B) % MOD = (( A % MOD ) + ( B % MOD )) % MOD
뺄셈 : (A - B) % MOD = (( A % MOD ) - ( B % MOD )) % MOD
곱셈 : (A * B) % MOD = (( A % MOD ) * ( B % MOD )) % MOD

처음에는 algorithm헤더(cmath, math.h이외)에 있는 제곱근(pow, double형)을 사용하여 구현했는데 이렇게 되면 이미 함수를 계산할때 정수형 범위를 넘어가게 됩니다. 그리고 모듈러 연산 법칙은 %앞에는 정수만 올 수 있기 때문에 강제 캐스팅을 했습니다.

    for (int i = 0; i < L; i++) {
        cin >> c;
        ans += (c - 'a' + 1) * (int)pow(31, i) % MOD;
    }

---

결과