반응형
Notice
Recent Posts
Recent Comments
Link
지구정복
[해쉬] 백준 - Hashing 본문
728x90
반응형
https://www.acmicpc.net/problem/15829
-문제해설
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 )
728x90
반응형
'데이터 엔지니어링 정복 > Algorithm' 카테고리의 다른 글
[수학] 백준 - 달팽이는 올라가고 싶다 (0) | 2021.07.24 |
---|---|
[문자열] 백준 - 팰린드롬수 (0) | 2021.07.24 |
[브루트포스] 백준 - 블랙잭 (0) | 2021.07.23 |
[수학] 백준 - 부녀회장이 될테야 (0) | 2021.07.23 |
[수학] 백준 - 벌집 (0) | 2021.07.23 |
Comments