[백준/파이썬/Python] 15829번 Hashing

문제

문제가 길어서 요약해보겠다. 

해시 함수는 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 

입력으로 들어오는 문자열은 영문 소문자(a, b, ..., z)로만 구성되어있으며, 각 문자에는 1부터 26까지의 번호가 붙는다. 이때 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다. 수열의 값을 모두 더한 후 유한한 범위의 출력을 갖기 위해 M으로 나눠준다면, 해시 함수의 식은 다음과 같다.

위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 해시 값이 같아져 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니 이를 개선해서, 수열의 각 항마다 고유한 계수를 부여하는 방법이 있다. 이를 수식으로 표현하면 아래와 같다.

보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 이 문제에서 r의 값은 26보다 큰 소수인 31로, M의 값은 1234567891로 설정되었다.

이제 위 식을 통해 주어진 문자열의 해시 값을 계산할 것이다. 

입력

첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.

입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.

출력

문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.

코드 초안

import math

r = 31
m = 1234567891

# 입력
l = int(input())
word = input()

# ord 함수를 이용하여 문자열을 숫자 리스트로 변환
num = []
for c in word:
    num.append(ord(c) - 96)

# 해시 값 계산
sum = 0
for i in range(l):
    sum += num[i] * math.pow(r, i)
sum %= m

print(int(sum))

 

ord(c) (ordinal)는 주어진 문자의 아스키 코드 값을 반환한다. 

'a'의 아스키 코드 값은 97이므로, 96을 빼주어 'a'의 값이 1이 되게 한다.

* 소문자는 ord(c) - 96, 대문자는 ord(c) - 64이다. 

 

그러나 이 방법을 사용했을 때 큰 길이의 문자열 입력에 대해서는 틀렸다고 나왔다.

리뷰

시간 초과가 원인인가 싶어서 math.pow(r, i) 대신 바로 r**i 를 적었는데, 통과되었다.

찾아보니 ** 연산자가 math.pow()에 비해 빠르고, 더 큰 수를 다룰 수 있다고 한다.

r = 31
m = 1234567891

l = int(input())
word = input()

num = []
for c in word:
    num.append(ord(c) - 96)

# 해시 값 계산
sum = 0
for i in range(l):
    sum += num[i] * r**i
sum %= m

print(int(sum))