[백준/JAVA] 15829 Hashing

Hashing

백준 15829번 Hashing 문제 링크

풀이

• (A*B) Mod N 의 경우 (A Mod N * B Mod N) Mod N 과 동일하다.
• r의 값이 int 자료형의 범위를 넘는 경우를 대비하여, 1234567891로 나머지 연산을 해준다.

---

제출 코드

import java.io.*;

public class Main {
    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 N = Integer.parseInt(br.readLine());
        String s = br.readLine();
        // M = 소수
        int M = 1234567891;
        // r = 자리의 계수, M과 r은 서로소 문제에서 값이 주어짐
        long r = 1;
        long sum = 0;

        // 각 자리의 알파벳을 a=1 ~ z=26 이라는 값으로 변환 후 Moduler M 연산을 한 값을 합에 추
        // long 자료형의 범위 제한에 따라 r이 1234567891 값을 넘지 않게 나머지 연산
        for (int i = 0; i < N; i++) {
            sum += ((s.charAt(i) - 'a' + 1) * r) % M;
            r = (r * 31) % M;
        }
        bw.write(String.valueOf(sum % M));
        bw.flush();
    }
}

---