[Java 자바] 백준 알고리즘 15829번 답 : Hashing

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

15829번: Hashing

 

 

이 문제는 50점 맞기는 쉽다..

문제는 문자열 길이 50이하의 테스트케이스인 Large 파트에서 점수를 얻으려면 추가로 고려해야하는 부분이 있다..ㅠㅠ

 

 

내가 이 문제 만점받느라고 좀 시간을 썼다,,^^

 

먼저 구글링해서 힌트를 좀 얻었다.

 

1. 모듈러연산의 성질

1) ( A + B ) mod M = ((A mod M) + (B mod M)) mod M

2) ( A * B ) mod M = ((A mod M) * (B mod M)) mod M

 

위의 성질을 적용하면 이 문제는 아래의 연산으로 변경할 수 있다.

 

2. long 타입

아무리 매번 모듈러 연산을 해준다지만, 길이가 길어질수록, 엄청나게 큰 숫자들이 더해질 것이다! 

그리고 나의 경우는 r을 매번 곱해줘서 제곱을 구현했는데, 이때도 매번 모듈러 연산을 해주더라도 int 범위를 넘어선다,,!

 

이때, Math.pow연산을 쓰면 50점은 받을 수 있지만 100점은 절대 불가,, 왜냐면 Math.pow(31,49)까지 가면,, long 범위도 벗어나버림... 그래서 차라리 매번 곱해주면서 모듈러 연산을 통해 크기를 줄여줘야함~~!

 

그래서 r로 사용하는 변수와 sum 변수는 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 N = Integer.parseInt(br.readLine());
        String s = br.readLine();
        int prime = 1234567891;
        long r=1;
        long sum = 0;

        for(int i=0;i<N;i++){
            sum += ((s.charAt(i)-'a'+1)*r)%prime;
            r = (r*31)%prime;
        }

        System.out.println(sum%prime);
    }
}