백준 JAVA 15829 Hashing

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

15829번: Hashing

사실 문제도 잘 이해가 안가서 문제 밑에 나와있는 힌트를 보고 풀었다.

그리고 풀었는데 계속 50점이 나와서 어떡하지 하다가 해싱 관련해서 지식이 없어 블로그를 찾아보게 되었다.

브론즈2인데 정답비율이 30% 인걸보면 역시 뭔가 있었다..

 

해당 문제를 풀려면 모듈러 연산의 성질 이라는 것을 적용해야 한다.

분배법칙 이라는 것인데, 간단히 말하면 31%M 이나 31이나 똑같다는 점을 이용한다는 것이다.

 

사실  mod 의 뜻이 프로그래밍에서 % 을 나타낸다는 것도 지금 알았다.

이거 뜻을 알고 다시 코드를 보니 대입만 잘하면 풀 수 있었다..

 

 

 

package BAEKJOON.Bronze.Ⅱ;

import java.util.Scanner;

public class NO15829 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int m = 1234567891;
        long n = sc.nextInt();
        String str = sc.next();
        long answer = 0;
        long pow = 1;

        for (int i = 0; i < n; i++) {
            answer += (str.charAt(i) - 'a' + 1) * pow % m;
            pow = pow * 31 % m;

        }
        answer = answer % m;
        System.out.println(answer);
    }
}

ㅠㅠ