[BOJ] 백준 15829 Hashing

출처: https://www.acmicpc.net/problem/15829

Approach

 Input 

5

abcde

 

 Output 

4739715

해당 문제는 문자열 Hash Function을 구현할 때,

어떤 Hash Function이 효율적인지 설명해주는 문제이다.

 

▶ [해시] Hash란? 

[해시] Hash란?

 

<알파벳 고유번호로 하는 경우>

    "a b c" → 1 + 2 + 3 = 6

    "c a b" → 3 + 1 + 2 = 6

    "b a c" → 2 + 1 + 3 = 6

위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 효율적이지 못하다.

좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다.

 

그렇기 때문에 수열의 각 항마다 고유한 계수를 부여하는 방식으로 처리하였다.

해당 방식이 얼마나 효율적인지, 왜 효율적인지에 대해서는 "수학자의 영역" 인 것 같다.

PS 에서는 Hash 구현에서 Key 충돌이 발생할 수 있으며, 이를 어떻게 처리할 것인가일 것 같다.

    ▶ [해시] Hash Chaining 기법 구현  

    ▶ [해시] Hash Open Address 기법 구현 

 

 

L 이 클 수 있기 때문에 unsighed long long과 long long 이용

수치적 계산은 나머지 연산(%)과 for문을 이용해 거듭 제곱할 수 있다.

(pow() 함수를 사용하는 경우에는 부분 점수 밖에 받지 못합니다.)

---

#include <stdio.h>

int L;
unsigned long long num;
long long R = 1, MOD = 1234567891;

char str[51];
int main() {
    // freopen("input.txt", "r", stdin);

    scanf("%d %s", &L, str);

    for (int i = 0; i < L; i++) {
        num += (str[i] - 'a' + 1) * R; num %= MOD;

        R *= 31; R %= MOD;
    }

    printf("%lu", num);
}