[Java] 백준 15829번 : Hashing

문제

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

 

 

접근 방법

1. 해시값이 어떻게 나오는지 원리에 대해 설명해주고 그것을 구현한 문제이다.
2. 문자열이 들어오면 일단 각 문자를 int로 변환하고 1, 31, 31^2, 31^3 순으로 곱하면 된다.
3. 하지만 여기서 주의할 점은 값이 long범위를 초과할수도 있으니 1234567891로 나누는것에 유의하자.
4. 또한 마지막 값인 sum값도 1234567891로 나누어 떨어질수 있으므로 한번 더 나누어 주자.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int L;
    private static long sum;
    private static long res = 1;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        L = Integer.parseInt(br.readLine());

        String line = br.readLine();
        for(int i = 0 ; i < L ; i++){
            int alphabet = line.charAt(i)-'a'+1;
            process(alphabet);
        }

    }

    //실행
    public static void process(int input) {
        sum += input*res % 1234567891;
        res = (res*31) % 1234567891;
    }


    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sum%1234567891);
    }
}