백준 15829: Hashing과 나머지 연산

백준 15829번 Hashing은 알파벳을 숫자로 바꾸고 각 자리에 31의 거듭제곱을 곱해 더하는 문제입니다.

거듭제곱을 그대로 키우지 않습니다

a부터 z까지를 1부터 26으로 바꿉니다. 첫 자리의 계수는 1로 둡니다. 다음 문자로 넘어갈 때마다 계수에 31을 곱합니다.

이 값을 계속 키우면 정수 자료형의 범위를 넘습니다. 그래서 (A × B) mod M = ((A mod M) × (B mod M)) mod M이라는 성질을 이용해 계수를 갱신할 때마다 M으로 나눈 나머지를 저장했습니다. M은 문제에서 주어진 1,234,567,891입니다. 코드의 r은 고정된 밑 31 자체가 아니라 각 자리에서 사용할 계수입니다.

코드의 계수와 합계는 long입니다. 나머지를 취하기 전 곱셈도 계산할 수 있어야 하므로 long을 쓰면서 계수의 크기도 제한해야 합니다.

제출 코드

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        String s = br.readLine();
        // M = 소수
        int M = 1234567891;
        // r = 자리의 계수, M과 r은 서로소 문제에서 값이 주어짐
        long r = 1;
        long sum = 0;

        // 각 자리의 알파벳을 a=1 ~ z=26 이라는 값으로 변환 후 Moduler M 연산을 한 값을 합에 추
        // long 자료형의 범위 제한에 따라 r이 1234567891 값을 넘지 않게 나머지 연산
        for (int i = 0; i < N; i++) {
            sum += ((s.charAt(i) - 'a' + 1) * r) % M;
            r = (r * 31) % M;
        }
        bw.write(String.valueOf(sum % M));
        bw.flush();
    }
}