BOJ_B2_15829

📁 [B2_15829] Hashing

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


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

		// **** input start ****
		int N = Integer.parseInt(br.readLine());

		String str = br.readLine();

		long sum = 0;
		long r = 1;
		for(int i=0; i<N;i++) {
			sum += ((str.charAt(i)-96) * r) % M;
			r = (r * 31) % M;
		}

		// **** input end ****
		System.out.println(sum%M);
	}
}

🤔 나의 생각

처음에 그냥 Math.pow() 로 풀었는데 50점이 나와서 문제를 제대로 봤다.. ㅋㅋ
문제를 보니 포인트는 %M 인 것 같다.
모듈러연산을 이용해 식을 전개할 수 있다.
(A+B)mod M = ((A mod M) + (B mod M)) mod M
그래서 모든 연산에 mod M을` 해주고
r과 sum 변수는 long을 사용하는것 !
왜냐면 50까지 간다면 범위를 훌쩍 넘어버리기 때문에 long 도 필수 이다.