[BOJ] 15829번 : Hashing

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

15829번: Hashing

 

 

문제 파악

1. 문자열의 길이가 주어지고 해당 길이를 만족하는 문자열이 주어진다.

2. 문제 설명에 나와있듯이 r의 값은 26보다 큰 소수인 31, M의 값은 1234567891로 정해져 있다.

3. 인덱스 위치 0부터 L-1까지 차수를 증가시키면서 ((해당 인덱스의 문자) - 'a' +1) * (31)^(인덱스) 값을 M으로 나눈 나머지를 구한다.

 

JAVA에는 BigInteger class가 있어서 BigInteger로써 문제를 해결하였다.

 

import java.io.*;
import java.math.BigInteger;

public class Main {
    static BigInteger rem = BigInteger.valueOf(1234567891);
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int len = Integer.parseInt(br.readLine());
        String str = br.readLine();

        BigInteger bigInteger = BigInteger.ZERO;

        int L = 0;

        for(int idx=0;idx<len;idx++)
        {
            int num = str.charAt(idx) -'a'+1;
            BigInteger result =getHashCode(num,L);

            bigInteger = bigInteger.add(result).remainder(rem);
            L++;
        }
        
        System.out.println(bigInteger);
    }

    private static BigInteger getHashCode(int num, int idx) {

        BigInteger exp = BigInteger.valueOf(31).pow(idx);

        BigInteger multiply = BigInteger.valueOf(num).multiply(exp).remainder(rem);

        return multiply;
    }
}