[Java] BOJ 15829 Hashing

문제 

문제 링크 https://www.acmicpc.net/problem/15829

• r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891로 한다.
• 위 식을 통해 주어진 문자열의 해시 값을 계산하시오.
• 첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.
• 입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.
• 문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.

아이디어

• 영어의 소문자를 아스키코드로 변환시켜 해당 아스키코드에 해시 값을 매칭시켜서 아스키코드를 key값, 해시 값을 value값으로 사용하는 HashMap을 사용하면 되겠다고 생각했다. 
  
  

겪은 시행착오

• 처음에 50점이 나왔다... 머가 문제인가 했더니 문자열 길이가 커질수록 31의 제곱수가 기하급수적으로 커져서 오버플로우가 생겨 나머지 50점을 못받은거였다. 
• 그래서 처음에는 Math.pow를 써서 제곱수를 계산했지만 for문을 통해 31을 일일이 곱해주면서 1234567891을 나눠 나머지를 구했다. 
• 다음부터 오버플로우도 생각하기..! 그리고 문제도 조금 더 꼼꼼히 읽기.. (처음에 1234567891 나누는걸 빼먹었다..ㅎ)

문제를 좀 더 꼼꼼히 풀자!

코드

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

public class BOJ15829 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        String s = br.readLine();

        // 해시 값 저장할 배열
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(26);

        int cnt = 1;
        // 소문자 아스키코드가 97 ~ 122
        // 아스키코드마다 해시함수 값 저장
        for(int i = 97; i <= 122; i++){
            hash.put(i, cnt);
            cnt = cnt + 1;
        }

        int hash_cnt = 0;
        long result = 0;

        for(int i = 0; i < s.length(); i++){
            // i번째 문자를 아스키코드로 변환
            int c = (int)s.charAt(i);

            // 변환한 아스키코드를 key 값으로 해당 해시 값인 value를 찾음
            int h = hash.get(c);

            long po = 1;
            // 해시 값 * 31^(숫자 해당 순번(0부터 시작)
            for(int j = 0; j < hash_cnt; j++){
                // 31을 계속 곱해준 후, 오버플로우가 나는 것을 방지하기 위해
                // 1234567891로 나눈 나머지
                po = (po * 31) % 1234567891;
            }

            // 나온 31 제곱값과 해시 값을 곱해줌
            po = h * po;

            // 더한수도 오버플로우가 날 수 있으므로 1234567891로 나눠줌
            result = (result + po) % 1234567891;

            // 숫자 순번 + 1
            hash_cnt = hash_cnt + 1;
        }

        System.out.println(result);
    }
}