C++) 15829, Hashing

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

문제 내용

소문자 알파벳의 연이은 문자열을 받을 때,

L=문자열의 길이(small:1 ≤ L ≤ 5/large1<=L<=50)

ai=문자열의 i-1번째 문자에 해당하는 알파벳(a=1, b=2, ㆍ ㆍ , z=26)

r=31, M=1234567891

이 H 식 구현하기

 

50점 나온 코드

#include <algorithm>
#include <iostream>
#include <math.h>
typedef long long int llint;
using namespace std;
llint n,Mod=1234567891,ans,k[51];
char ar[51];
string L;
int main(){
  cin>>n;
  cin>>L;
  for(int i=0;i<n;i++){
    ar[i]=L[i];
    k[i]=ar[i]-96;
  }
  for(int i=0;i<n;i++){
    ans+=k[i]*pow(31,i);
  }
  cout<<ans%Mod;
}

for문 안에 있는 96의 경우 'A'의 아스키코드값에서 1을 뺀 값인 ai를 나타낸다.

H 식 자체를 그대로 구현했으나 알고 보니 n이 50일 때(k [49]*pow(31, i))만 해도 unsigned long long int의 값을 넘었다.

그래서 50점이 나왔다.

 

100점 나온 코드

#include <iostream>//15829, Hashing
typedef long long llint;
using namespace std;
llint ans, Pow = 1, Mod = 1234567891;
short n;
string L;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> L;
    for (short i = 0; i < n; i++) {
        ans = (ans + (L[i] - 96) * Pow) % Mod;
        Pow = (Pow * 31) % Mod;
    }
    cout << ans;
}

ans에 값을 더할 때에, 제곱을 할때에 모드를 나누어서 값을 넘지 않도록 하였다.

math를 쓰지 않고도 제곱을 구현할 수 있을까를 생각하다가 한 변수(Pow)에 31을 i만큼 계속 곱해주면 제곱을 구현하기에 math.h를 안 써서 제곱을 구현했다. 이 문제를 푸는 핵심은 변수의 데이터 타입에 따른 크기를 알고 있는가? 무엇보다 범위가 커지는 것에 따른 MOD의 필요성이 이번 문제의 핵심이라 생각한다.