[코딩테스트/ 백준 알고리즘] 15829번 : Hashing (Java, 자바 풀이)

문제

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

15829번: Hashing

---

문제 설명

---

문제 풀이

 나머지 연산의 분배법칙을 모르면 풀기 까다로운 문제였다.

(A * B) % m = (A % m) x (B % m) % m

이게 곱셈에서의 나머지 연산 분배법칙이다. 

 

 이 문제는 파이썬이면 아무 생각 없이 풀 수 있는 문제(파이썬은 수 범위가 무한이니까)지만 그 외 언어를 쓴다면 나머지 연산에 작업을 해주어야 한다. 그렇지 않으면 31⁵⁰이라는 엄청난 범위의 수를 담아낼 자료형이 없기 때문이다.

 

Aⁿ % m = (Aⁿ⁻¹ x A) % m = (Aⁿ⁻¹ % m) x (A % m) % m

때문에 위와 같은 연산을 통해 수를 Java에서 담아낼 수 있는 범위로 조절하는 것이 필요했다.

---

코드

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int length = Integer.parseInt(br.readLine());
        int r = 31;
        int m = 1234567891;
        long sum = 0;
        long mod = 1;
        char[] ch = br.readLine().toCharArray();

        for(int i = 0; i < length; i++) {

            sum += (((int)((ch[i] - 'a') + 1)) * mod);
            mod = (r * mod) % m;
        }
        System.out.println(sum % m);
    }
}