[BOJ] 15829. Hashing

백준 온라인 저지에 있는 15829번 Hashing 문제 풀이입니다. 

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

처음에는 31^i를 구하는 부분에서 pow(31, i)를 썼더니 부분 점수를 받았습니다.

L이 커졌을 때 pow(31, i) 부분 때문에 시간복잡도가 엄청나게 커졌나봐요.

31^i는 1, 31, 31*31, 31*31*31 ... 이라서 이전 31^i에 31을 한번 더 곱하기만 하면 되는데

괜히 필요없는 함수를 호출하면서 시간복잡도를 크게 만들어버렸어요...

그래서 아래와 같이 바꿨더니 전체 정답이 되었습니다!

중복되는 부분, 생략할 수 있는 부분을 고민하면서 짜야하는데 나름 신경쓰다가도 생각없이 짤 때가 있네요...

반성해야겠습니다. 🤧

 

❗️중복되는 부분, 생략할 수 있는 부분 고민하기❗️

 

#include <iostream>
#define MOD 1234567891

using namespace std;

int l;
string input;

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> l >> input;
    
    long long result = 0;
    long long temp = 1;
    
    for(int i=0; i<l; i++) {
        result += ((input[i]-'a'+1)*temp)%MOD;
        temp *= 31;
        temp %= MOD;
    }
    
    cout << result%MOD;
    
    return 0;
}