[백준 15829] 해시 (C#, C++) - soo:bak

문제 링크

15829번 - 해시

설명

이 문제는 문자열을 특정 방식으로 정수로 변환하여 해시값을 계산하는 문제입니다. 주어진 규칙은 아래와 같습니다:

• 문자열의 각 알파벳을 숫자로 변환 (a → 1, …, z → 26)
• \(i\)번째 문자는 \(31^i \times \text{val}\) 방식으로 가중합
• 모든 항은 모듈로 연산 \(1234567891\)을 포함하여 누적합

이 방식은 실제 해싱 알고리듬(예: 롤링 해시)에서 자주 사용하는 다항식 해싱과 유사합니다.

수식 정리

주어진 문자열 str에 대해 다음과 같이 계산합니다:

\[\text{Hash} = \sum_{i=0}^{n-1} ( \text{val}_i \cdot 31^i )\mod 1234567891\]

단, \(\text{val}_i = \text{str}[i] - \text(a) + 1\) 로, 각 문자는 알파벳 'a'를 기준으로 1부터 시작하는 정수로 변환됩니다.

---

Code

[ C# ]

namespace Solution {
  class Program {
    const long MOD = 1234567891;

    static void Main(string[] args) {
      var len = int.Parse(Console.ReadLine()!);
      var str = Console.ReadLine()!;
      long sum = 0, pow = 1;

      for (int i = 0; i < len; i++) {
        var val = str[i] - 'a' + 1;
        sum = (sum + val * pow % MOD) % MOD;
        pow = (pow * 31) % MOD;
      }

      Console.WriteLine(sum);
    }
  }
}

[ C++ ]

#include <bits/stdc++.h>
#define MOD 1234567891

using namespace std;
typedef long long ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int lenStr; string str; cin >> lenStr >> str;

  ll sum = 0;
  for (int i = 0; i < lenStr; i++) {
    ll c = str[i] - 96;
    for (int j = 1; j <= i; j++)
      c = (c * 31) % MOD;
    sum += c % MOD;
    sum %= MOD;
  }
  cout << sum << "\n";
  return 0;
}