백준 15829번: Hashing 문제 (C#)

오늘은 백준 15829번 해싱 문제를 풀어봤다.
문자열을 주어진 방식으로 해싱해서 정수값을 출력하는 문제인데,
각 문자를 정수로 변환하고 거기에 r^i를 곱한 뒤 모두 더하는 방식이다.

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

🧩 핵심 규칙

문자는 'a' = 1, 'b' = 2, ..., 'z' = 26으로 변환

각 문자의 위치 i에 대해 r^i를 곱함 (r = 31)

결과값은 계속 mod 1234567891을 해줘야 한다

💡 배운 점

r^i를 Math.Pow()로 하면 실수 오차가 생길 수 있어서 long pow = 1; pow = (pow * r) % mod; 식으로 누적하면서 처리해야 한다.

result도 매번 누적하면서 mod 해주는 게 중요. 안 그러면 오버플로우 남.

단순한 해싱 로직처럼 보여도 오버플로우나 실수형 계산 오차 때문에 은근히 까다롭다.

using System;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        string s = Console.ReadLine();

        long result = 0;
        long r = 31;
        long mod = 1234567891;
        long pow = 1;

        for (int i = 0; i < s.Length; i++)
        {
            int value = s[i] - 'a' + 1;
            result = (result + value * pow) % mod;
            pow = (pow * r) % mod;
        }

        Console.WriteLine(result);
    }
}

간단한 문제인데, pow와 result가 어떤 순서로 어떻게 갱신되는지 꼼꼼히 따져보니까 흐름이 딱 잡혔다.
다음에 비슷한 해싱 문제가 나오더라도 당황하지 않고 풀 수 있을 것 같다.