[해쉬] 백준 - Hashing

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

15829번: Hashing

 

-문제해설

l로 문자열 길이를 입력받고 다음 줄에 문자열을 입력받는다.

이때 a=1, b=2, c=3, d=4, ... ,z=26이다.

 

만약 주어진 문자열이 abcde라면 해당 문자열의 해시값을 얻는 방법은 

1*31^0 + 2*31^1 + 3*31^2 + 4*31^3 + 5*31^4 가 되는데 

만약 문자열의 길이가 5보다 크고 50이하이면 값이 너무 커지므로 매번 계산할 때마다 m값으로 나머지를 구해야 한다.

 

그리고 a=1, b=2 ,.... 를 얻는 방법은 문자 a의 아스키코드값은 97이므로 

주어진 문자 - 'a' + 1을 해주면 된다.

 

a가 주어졌을 경우

'a' - 'a' + 1 = 97 - 97 + 1 = 1이 된다.

 

 

-자바

package hashing;

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

public class BJ15829 {
	private static BufferedWriter bw = 
			new BufferedWriter( new OutputStreamWriter(System.out));
	private static int l;
	private static long sum;
	private static String s;
	private static int r = 31;
	private static final int m = 1_234_567_891; 
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		l = Integer.parseInt( br.readLine() );
		s = br.readLine();
		
		long tmp = 1;
		for( int i=0; i<s.length(); i++ ) {
			sum = ( sum + ((s.charAt(i)-'a'+1 ) * tmp) ) % m;
			tmp = (tmp * r) % m;
		}
		
		bw.write( sum%m + "\n" );
		bw.flush();
		bw.close();
		br.close();
	}
}

 

-파이썬

l = int( input() ); s = input(); ans = 0; tmp = 1; m = 1234567891
for i in range( len(s) ):
    ans = ( ans + ( ord(s[i])-ord('a')+1 )*tmp ) % m
    tmp = (tmp*31) % m
print( ans )