[JAVA] 백준 15829번: Hashing

 

---

문제

• 문자열 길이와 문자들이 주어질 때, 주어진 해시 함수를 이용해 계산한 해시 값을 정수로 출력하는 문제.

 

아이디어

• 주어진 그대로 구현한다.
• L이 50을 넘어가면 31^51 이라는 어마무시한 크기의 숫자가 나오므로 매번 M 값으로 나누어 준다.
• 혹시라도 발생할 오버플로우를 방지하기 위해 연산에 사용되는 tmp 변수를 long 타입으로 지정한다.

 

풀이

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

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

        int r = 31;
        int M = 1_234_567_891;

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

        long hash = 0;
        for(int i=0; i<L; i++) {
            long tmp = str.charAt(i)-96;
            for(int j=0; j<i; j++) {
                tmp *= r;
                tmp %= M;
            }
            hash += tmp;
            hash %= M;
        }

        System.out.println(hash);
    }
}

 

 

채점 결과

15829번 채점 결과

기타

•   기본적인 롤링 함수라고 하니 잘 숙지해둬야겠다.

 

문제 링크

• 15829번: Hashing (acmicpc.net)