★[python_파이썬_Pass]백준_15829번_Hashing_구현/해싱_풀이

공부하는허딩크 : https://www.youtube.com/live/AgMXuQAl4JE?feature=shared

※회사 점심시간 활용

 

일단 시그마, mod같은 용어들이 낯설다.

시그마는 뭐 모든 합계인걸 알겠으나 mod는 처음 보는 것 같다.

밑에 힌트가 있다.

 

즉, 주어진 알파벳의 고유 번호와 인덱스를 활용해서 a(고유번호로 변경) * 31 ** index의 sum을 하면 될 것 같다.

 

<첫번째, 두번째, 세번째 시도 : 50점_이렇게 표현되는거 처음 봤다.>

string 모듈을 처음 써봤다.

string.ascil_lowercase를 사용하면 a-z까지 문자열을 만들 수 있다. (string.ascil_uppercase, string.ascil_letters등이 있다.)

※sring.ascil_letters는 a-z, A-Z까지 순서대로 포함하는 문자열이다. filter작업할때 유용할 것 같다.

''.join([char for char in text if char in string.ascil_letters])

 

내가 사용한 건 딕셔너리를 활용해서 Alpha의 인덱스 순서대로 1~26까지 key와 value를 설정하고

result[j]의 value는 고유넘버가 매칭됨으로 아래와 같이 작성했다.

import sys

import string

input = sys.stdin.readline

#이거 나중에 문제 자체의 의미 리뷰 필요 : 문제가 이해가 안됨.

N = int(input())

alpha = list(''.join(map(str, input().split())))

Alpha = list(string.ascii_lowercase)

result = {}

answer = 0

for i in range(1, 27):

  result[Alpha[i - 1]] = i

for i, j in enumerate(alpha):

  answer += result[j] * 31 ** i

print(answer)

 

chr()라이브러리를 활용해서 알파벳 문자열을 생성했다.

아스키 코드값 'a' : 97 ~'z' : 122 / 'A' : 65 ~ 'Z' : 90 이거 기억해두면 편하다.

import sys

input = sys.stdin.readline

N = int(input())

alpha = list(''.join(map(str, input().split())))

Alpha = list(''.join(chr(i) for i in range(97, 123)))

result = {}

answer = 0

for i in range(1, 27):

  result[Alpha[i - 1]] = i

for i, j in enumerate(alpha):

  answer += result[j] * 31 ** i

print(answer)

import sys

input = sys.stdin.readline

N = int(input())

alpha = list(''.join(map(str, input().split())))

result = {}

answer = 0

for i in range(26):

  result[chr(i+97)] = i + 1

for i, j in enumerate(alpha):

  answer += result[j] * 31 ** i

print(answer)

 

<네번째 시도 : 맞았습니다.>

mod는 파이썬에서  modulo연산을 의미하며 나눗셈의 나머지를 구하는 연산이다.

문제에서도 아래와 같이 나눠주자는 조건이 있다.

혹시나 하는 마음에 M을 변수로 지정해서 answer % M을 했는데 통과가 되었다. 

아직도 잘 모르겠다.....

import sys

input = sys.stdin.readline

N = int(input())

alpha = list(''.join(map(str, input().split())))

M = 1234567891

result = {}

answer = 0

for i in range(26):

  result[chr(i+97)] = i + 1

for i, j in enumerate(alpha):

  answer += result[j] * 31 ** i

print(answer % M)

 

<chat gpt 도와줘.. 아래와 같이 답을 받았는데 잘 모르겠다... 일단 pass>

해시 함수에서 answer % M을 하는 이유는 정수 오버플로우를 방지하고, 해시 값의 범위를 제한하기 위해서입니다. 이를 조금 더 자세히 설명하면 다음과 같습니다.

1. 정수 오버플로우 방지

문자열의 길이가 길어지면 answer 값이 매우 커질 수 있습니다. 특히, 지수로 곱해지는 31 ** i의 값은 i가 커질수록 빠르게 증가합니다. 이러한 큰 수를 다루다 보면 컴퓨터가 표현할 수 있는 정수의 최대 범위를 넘어가는 정수 오버플로우가 발생할 수 있습니다.

예를 들어, Python은 일반적으로 큰 정수도 자동으로 처리할 수 있지만, 다른 언어에서는 정수의 최대 크기가 제한되어 있습니다. 오버플로우가 발생하면 잘못된 결과가 나올 수 있으므로 answer % M을 통해 중간 계산 단계에서 나오는 값을 M으로 나눠줌으로써 오버플로우를 방지합니다.

2. 해시 값의 범위 제한

해시 함수는 무한한 입력을 유한한 범위의 값으로 매핑하는 것이 목적입니다. answer % M을 사용하여 answer를 M으로 나눈 나머지를 계산하면, 결과값이 항상 0에서 M-1 사이의 값으로 제한됩니다.

이는 해시 테이블에서 해시 값을 인덱스로 사용할 때 유용합니다. 예를 들어, 해시 테이블의 크기가 M일 때, 계산된 해시 값을 M으로 나눈 나머지로 사용하면 항상 테이블의 유효한 인덱스를 얻을 수 있습니다.

3. 해시 충돌 최소화

문제에서 M은 소수로 주어졌습니다. 해시 함수의 출력을 소수로 나눈 나머지로 제한하는 것은 해시 충돌을 줄이는 데 도움이 됩니다. 두 개의 다른 문자열이 같은 해시 값을 가질 확률을 줄일 수 있기 때문입니다.

정리

따라서, answer % M을 하지 않으면 해시 값이 너무 커져서 문제가 발생할 수 있으며, 해시 함수의 기본적인 특성을 유지할 수 없습니다. answer만 출력하는 것은 본래 해시 함수의 목적에 맞지 않기 때문에, 항상 answer % M을 사용해야 합니다.