[백준:15829/Python] Hashing 문제

해시함수 란 ? 

임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 
자료의 저장과 탐색에 쓰인다. 

 

문제 요약 

문제 a ~ z 까지 고유한 번호 1 ~ 26으로 부여해 준다. 

입력받은 영어로 된 문자열을 고유한 번호로 바꿔준 뒤, 이 수열을 하나의 정수로 치환하기 위해 

모든 수열을 더해준다. 

그리고 다 더한 값을 유한한 범위를 갖기 위해 적당히 큰 수 M 으로 나눠준다. 

이렇게 나오게 되는 것이 해시값이다. 

 

위의 설명을 수식으로 표현했을 때

하지만, 서로 다른 문자열이라도 동일한 해시값을 가질 수 있으며, 이를 해시충돌이라고 한다. 

이러한 해시충돌을 줄이기 위해 수열의 각 항마다 고유한 계수를 부여하면 되는데 

가장 대표적인 방법이 항의 번호에 해당하는 만큼 특정한 숫자 r을 거듭제곱해서 곱해준 다음 더하는 것이다. 

고유한 계수를 추가한 수식 표현방식

이 문제에서는 r, m 을 지정해 주었고 이들은 서로소인 숫자로 하는 것이 일반적이다. 

r 은 26 보다 큰 소수 31,  M 은 1234567891 (소수)로 지정해 준다. 

 

문제 풀이 

먼저 내가 푼 정답은 공유해보자면, 아래와 같다. 

import sys
N = int(input())
L = sys.stdin.readline() # 문자열 

# 1 ~26 (인덱스에 +1)
e = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

# 각 항을 더해주는 변수 
sum = 0
# 고유한 번호를 더 고유하게 만들어주는 숫자 부여 
r = 31 

# r과 서로소인 M
M =  1234567891

# 각 하나의 문자열마다 고유한 번호로 바꾼 뒤, 더해주는 반복문 만들기
for i in range(len(L)) : 
  if(L[i] != '\n') :  # i 에 줄바꿈도 넘어가서 제외해주기-> 넘어가는 이유가 readline으로 풀어서이다. 
    sum += (e.index(L[i])+1) * (r**i) # 고유한 번호 더해주기 

# 다 더한 것을 가장 큰 숫자 M으로 나눠주기 (정수로 출력)
# 여기서 % 로 나눠준 이유는 수식에 Mod M 이라고 되어있는데 
# 이 Mod 의 의미가 M 으로 나눈 뒤 나머지를 리턴한다는 의미이기 때문이다. 
print(sum%M)

index() 함수는 문자열을 인자로 받아서, 해당 문자열 위치의 인덱스를 반환한다.

 여기서는 e 에 담긴 a~z 문자를 찾아서, 해당 위치의 인덱스를 반환하는데 이때 인덱스는 기본적으로 0부터 시작하기 때문에 +1을 더하여 고유한 번호 1~26인 것에 맞춰준 것이다. 

 

사실 처음에는 M 을 넣고 계산하지 않아도, ide로 테스트케이스 대로 구현했을 때는 똑같이 정답이 나오길래 

그냥 제출을 해보았었다. 왜냐하면 힌트에서도 M의 계산이 따로 없었어서 내가 이해를 잘 못했다고 생각했었다. 

아래가 그렇게 제출했던 풀이 이다. 

import sys
N = int(input())
L = sys.stdin.readline() # 문자열 

# 1 ~26 (인덱스에 +1)
e = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

# 각 항을 더해주는 변수 
sum = 0
# 고유한 번호를 더 고유하게 만들어주는 숫자 부여 
r = 31 


# 각 하나의 문자열마다 고유한 번호로 바꾼 뒤, 더해주는 반복문 만들기
for i in range(len(L)) : 
  if(L[i] != '\n') :  # i 에 줄바꿈도 넘어가서 제외해주기 
    sum += (e.index(L[i])+1) * (r**i) # 고유한 번호 더해주기 

# 다 더한 것을 가장 큰 숫자 M으로 나눠주기 (정수로 출력)
print(sum)

그런데 점수배점이 50점만 부여가 되길래, M 계산을 추가해서 맨 위의 풀이와 같이 제출했더니 100점으로 부여가 됐다. 

원래 M 같은 소수의 큰 숫자로 나누는 이유가 유한한 범위를 지정해 주기 위해서인데,

M으로 나누지 않아서 무한한 범위를 갖게 돼서 그랬던 것 같다. 

 

추가적으로 e 에 저렇게 하나하나  a~z까지 적는 방식보다 더 간단한 방식이 있는 것 같아서 알아보니 

sum += (ord(L[i])-96)*(r**i)
# a 가 ASCII 코드로 97 이어서 -96 으로 계산을 하는 게 더 간단하다.

a의 ASCII 코드가 97이고 z의 ASCII 코드가 122 인 것을 생각하니 96을 빼면 되는 것이었다. 

 

이 해시함수 형식이 자주 쓰인다고 하니 기억해두는 게 좋을 것 같아서 기록해 본다.