[Python] 15829 Hashing

문제

https://www.acmicpc.net/problem/15829

풀이과정

• 영문 소문자만 입력한다.
• 입력한 문자열을 해시를 통해 특정 해시값으로 변환한다.

r= 31 에 항의 거듭제곱을 하고 1234567891을 나누어서 출력한다.

• a ~ z까지 각각 1 ~26을 의미한다.
• 하나씩 입력하는 것은 비효율 적이다.
• a의 아스키 코드는 97 이고, z의 아스키 코드는 122 → 96을 빼주면 1 ~ 26
• 처음 생각해본 알고리즘

  # 문자열의 길이 입력
  # 영문 소문자 입력
  # 소문자를 각각의 배열에 담기
  # 해시 처리하기
  # 문자열의 아스키코드 값 - 96 한 상태만큼 r(31)을 거듭제곱 하기
  # 값 출력하기

  코드 작성해보다가 굳이 배열에 담을필요 없다고 판단하여 소문자를 배열에 담는 과정을 생략해보았다.

  l = int(input())
  s = input()
  result = 0
  
  for i in range(l):
      result += (ord(s[i]) - 96) * (31 ** i)
  
  print(result)

  → 50점이 나왔다. 틀리거나, 버그가 발생하거나 그랬는데 점수가 나온건 처음인 것 같다.
  
• 원인

  수학 기호를 보면 M을 mod해주는데, 나머지연산을 안해서 반만 맞았던 것이였다.
  
  ```python
  l = int(input())
  s = input()
  result = 0
  
  for i in range(l):
      result += (ord(s[i]) - 96) * (31 ** i)
  
  print(result % 1234567891)
  ```

  메모리: 31256KB
  시간: 48ms