(매일 BOJ) Python 15829번 해싱

🔍 문제 요약

문자열이 주어졌을 때, 다음과 같은 해시 함수를 사용하여 문자열의 해시 값을 계산합니다:

공식:
H=∑i=0l−1(ai×ri)mod  MH = \sum_{i=0}^{l-1} (a_i \times r^i) \mod MH=∑i=0l−1​(ai​×ri)modM

• lll: 문자열의 길이
• aia_iai​: i번째 문자의 아스키 코드 값을 숫자로 변환한 값 (예: 'a'는 1, 'b'는 2, ..., 'z'는 26)
• rrr: 31
• MMM: 1234567891

---

🧮 입력

• 첫째 줄: 문자열의 길이 lll (1 ≤ lll ≤ 50)
• 둘째 줄: 문자열 (소문자 a~z)

---

✅ 출력

• 해시 값을 출력

1차 코드 / 50점

result = result % 1234567891

를 빼먹었다.

num = int(input())

abc = list('abcdefghijklmnopqrstuvwxyz')

text = list(input())

result = 0

buffer = 0

for i in range(num):

    for o in range(len(abc)):

        if text[i] == abc[o]:

            buffer = o+1

    result += buffer*31**i

print(result)

 

2차 코드

num = int(input())

abc = list('abcdefghijklmnopqrstuvwxyz')

text = list(input())

result = 0

buffer = 0

for i in range(num):

    for o in range(len(abc)):

        if text[i] == abc[o]:

            buffer = o+1

    result += buffer*31**i

result = result % 1234567891

print(result)

 

그리고 이와같이 개선할 수 있다.

 

 

• 기존 방식:
• for o in range(len(abc)):
      if text[i] == abc[o]:
          buffer = o + 1

 

• 개선 방식:
• buffer = ord(text[i]) - ord('a') + 1