[백준] 15829번 : Hashing – JAVA [자바]

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

15829번: Hashing

 

---

• 문제

 

---

• 문제 풀이

백준 15829번 Hashing은 브론즈 2 난이도의 문자열 및 해싱 문제이다. 이 문제에서는 소문자로만 이루어진 문자열이 1개가 주어지고 이 문제에서 주어진 해시함수를 써서 구한 해시값을 출력하면 된다.

 

문제에서 주어진 해시함수는 다음과 같다.

 

 

여기서 r은 31, 그리고 M은 1234567891이다.

 

이 문제에서는 L의 값은 1부터 100까지 가능하다. 따라서, 수가 매우 커질 수 있으므로 여기서는 BigInteger (큰 수 다루기)를 이용해서 풀겠다. 

 

우선 출력할 답 ans를 BigInteger 형태로 선언한다. 그리고 문자열에서 각 인덱스에 있는 소문자 알파벳마다 처리를 해줘야 하므로 이 인덱스에 있는 알파벳을 c라고 하겠다.

 

이 문제에서 해시값을 구할 때 a는 1로, z는 26을 써서 구한다는 것을 확인할 수 있다. 따라서, a의 아스키코드는 97이므로 (int) c - 96을 해주면 된다.

 

이제, 문제에서 나온 공식을 이용해서 문제를 풀면 된다. 자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int r = 31;
        int m = 1234567891;
        int n = Integer.parseInt(br.readLine());
        BigInteger ans = new BigInteger("0");
        String s = br.readLine();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            long ascii = (int)c - 96;
            for (int j = 0; j < i; j++) {
                ascii *= 31;
                ascii %= m;
            }
            BigInteger b = new BigInteger(String.valueOf(ascii));
            ans = ans.add(b);
            ans = ans.remainder(new BigInteger(String.valueOf(m)));
        }
        System.out.print(ans);
    }
}