[백준] 15829.Hashing(Java8)

문제

풀이

package solved2;

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{
		//Hashing
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int l = Integer.parseInt(br.readLine());//문자열의 길이
		String str = br.readLine();//문자열
		int ch;//문자
		long hash = 0;//해시 값
		
		for(int i = 0; i < l; i++) {
			ch = str.charAt(i) - 'a' + 1;
			hash += ch * hash(i);
		}
		
		System.out.println(hash % m);
		
		br.close();
	}
	
	public static long hash(int b) {
		return b == 0 ? 1 : 31 * hash(b - 1) % m;
	}

}

팁

- 모듈러 연산의 속성은 다음과 같습니다. 해당 문제에서는 1번과 3번 속성을 사용합니다.

1. (a + b) mod n = {(a mod n) + (b mod n)} mod n

2. (a - b) mod n = {(a mod n) - (b mod n)} mod n

3. (a * b) mod n = {(a mod n) * (b mod n)} mod n

- M의 값은 1234567891로 설정한다.

static final int m = 1234567891;

- l만큼의 길이를 가진 문자열을 사용해 해시값을 구한다.

이 때, ch를 int로 선언하고 다음과 같이 값을 대입하면 (a, b, ..., z)를 (1, 2, ..., 26)로 나타낼 수 있다.

for(int i = 0; i < l; i++) {     
	ch = str.charAt(i) - 'a' + 1;
	hash += ch * hash(i);        
}

- 해시함수 구하기

처음 해시 함수를 구할 때, Math.pow(31, i)를 사용했지만 l이 증가하면서  시간복잡도가 증가하여 50점밖에 얻지 못했다.

이를 보완하여 오버플로가 발생하지 않도록 매번 계산할 때마다 m값으로 나머지를 구하여 계산하고 hash값을 long형으로 선언하였다.

public static long hash(int b) {             
	return b == 0 ? 1 : 31 * hash(b - 1) % m;
}

- 결과 출력하기

System.out.println(hash % m);

출처

15829번: Hashing