[백준] 15829번 - Hashing (브론즈 2)

1. 문제

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

15829번: Hashing

---

 

2. 접근 방식

• 1차 : 문제에서 알려준 공식대로 구현 -> 50점, 작은 문자열에서는 잘 동작하지만 큰 문자열에서는 시간초과
• 2차 :  합동식 활용 A * B mod C -> (A mod C) * (B mod C) -> 통과

---

 

3. 코드

• 1차 코드

#include<iostream>
#include <cmath> 

typedef unsigned long long ll;

using namespace std;

int main() {
    int str_len;
    cin >> str_len;
    string str;
    cin >> str;

    int a, r = 31, M = 1234567891;
    ll sum = 0;

    for (int i = 0; i < str_len; i++) {
        a = (str[i] - 'a') + 1;
        sum += a * pow(r, i);
    }

    cout << sum % M << "\n";
}

• 2차 코드

#include<iostream>

using namespace std;

typedef unsigned long long ll;

int main() {
    int str_len;
    cin >> str_len;

    string str;
    cin >> str;

    ll r, sum = 0, a;
    int M = 1234567891;

    for (int i = 0; i < str_len; i++) {
        a = (str[i] - 'a') + 1;

        r = 1;
        for (int j = 0; j < i; j++) {
            r *= 31;
            r %= M;
        }

        sum += a * r;
        sum %= M;
    }
    
    cout << sum;
}

---

 

4. 결과