문자열. Hashing

문제

해시 함수를 적용해 각 알파벳 문자열을 유일한 수에 대등하도록 하려는 시도. 비둘기집의 원리지만, 최소한 줄이도록 노력.
먼저, r = 31, M = 1234567891 이다. a~z = 1~26으로 대응된다. (a)

해결방향성

BigInteger를 사용해야한다. 제곱을 할때도 BigInteger 방식으로 해야하므로 사칙연산을 모두 BigInteger 방식으로 해야한다고 생각하면 편하다.

코드

package string;

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

public class Hashing {
    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 L = Integer.parseInt(br.readLine());

        String s = br.readLine();

        char[] chars = s.toCharArray();

        // a == 1 ~ z == 26
        BigInteger summation = new BigInteger("0");
        for (int i = 0; i < L; i++) {
            int alphaToNum = chars[i] - 'a' + 1;
            BigInteger square = new BigInteger("1");
            for (int j = 0; j < i; j++) {
                square = square.multiply(BigInteger.valueOf(31));
            }
            square = square.multiply(BigInteger.valueOf(alphaToNum));
            summation = summation.add(square);
            summation = summation.remainder(BigInteger.valueOf(1234567891));
        }

        bw.write(String.valueOf(summation));

        bw.flush();
        br.close();
        bw.close();
    }
}

결론

BigInteger를 이용하는 좋은 예제. 요즘 long 범위까지 초과하는 문제가 자주 나오는데, 알아 놓는게 좋다. 브론즈에 이런 좋은 문제가 있어서 좋았다. 핵심 부분은 역시 BigInteger 선언, multiply, add, remainder 부분.