[백준] 15829번 Hashing -자바(JAVA)

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

15829번: Hashing

아무생각 없이 풀고 제출했다가 50점 받고 뭐지???? 했던 문제이다.

int 대신 long 타입을 사용했음에도 불구하고 50점이 나오는데, 그 이유는 31의 제곱수를 계산할때 overflow가 나기 때문이었다. Math.pow()함수를 사용했다면 주의하도록 하자.

이를 해결하기 위해 구글링을 좀 해봤는데 모듈러 연산의 성질 중 분배법칙을 이용하면 overflow를 해결할 수 있다고 한다.

주로 큰 수로 나눈 나머지를 구하라는 문제에서, 단순히 결과값에 %를 취하기 보단 연산 과정 중에서도 %를 취해야 하는 경우가 많다고 한다.

모듈러 연산의 성질

모듈러 연산은 분배법칙이 성립한다. 아래 성질을 이용하여 코드를 짜주도록 하자.

참고로 나눗셈은 분배법칙을 적용할 수 없어서 다른 방법을 써야한다고 한다.(페르마 소정리라고 하는데 그게 뭔진 아직 공부 안함)

(A+B) mod C = (A mod C + B mod C) mod C

(A - B) mod C = (A mod C - B mod C) mod C

(A * B) mod C = (A mod C * B mod C) mod C

 

문제 페이지에 나와있는 수식에 덧셈의 분배법칙을 적용하여 아래와 같이 풀어보았다.

이대로 코드를 짠다면 r의 거듭제곱과정에서 overflow가 발생할 수 있기 때문에, 곱셈의 분배법칙도 적용해줘야 한다.

31%M이나 31이나 똑같다는 점을 이용해서 불필요한 %M은 생략하고 짠 코드는 다음과 같다.

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 bw = new BufferedReader(new InputStreamReader(System.in));
		int L = Integer.parseInt(bw.readLine());
		String str = new String(bw.readLine());
		long sum = 0;
		long pow = 1;
		char[] arr = str.toCharArray();
		for(int i = 0; i < L; i++)
		{
			sum += (arr[i] - 'a' + 1) * pow % M; //분배법칙
			pow = pow * 31 % M; //분배법칙
		}
		long hash = sum % M;
		System.out.println(hash);
	}
}

 

눈물의 100점 T^T....