[백준] 15829 - Hashing

 

문제 출처 : https://www.acmicpc.net/problem/15829\

 

문제 정리

입력으로 들어오는 문자열은 영문 소문자로만 구성되어 있음.

알파벳 a~z는 1~26의 고유한 번호로 치환할 수 있음.

따라서 문자열을 수열로 변환할 수 있음. e.g)abba->1,2,2,1

해시값을 계산하기 위해서 문자열, 즉 수열을 하나의 정수로 치환할 것임.

수열을 모두 더하고 M으로 나눌 것임.

수열의 각 항의 번호에 해당 하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더함.

특정한 숫자 r은 31이며 M은 1234567891임.

 

 

입력

첫 줄에는 문자열의 길이 L이 들어온다.

둘째 줄에는 영문 소문자로 이루어진 문자열이 들어온다.

 

출력

문자열을 해시값으로 계산하여 정수로 출력한다.

 

풀이 방법

1. 문자열을 한글자씩 읽으면서 아스키코드로 변환하고 96을 빼서 1~26의 수로 치환한다.
2. for문 돌면서 계산한다.

 

작성한 코드

 

import sys

L = int(sys.stdin.readline().strip()) 
string = sys.stdin.readline().strip()
result = 0

for i in range(L): 
    number = ord(string[i])-96
    result+=number*pow(31,i)

print(result%1234567891)

 

 

알파벳 순서대로 숫자로 변환해야 한다는 점을 보고 아스키코드를 활용하면 되겠다는 생각이 바로 들어서 비교적 빨리 풀었다.

처음에는 숫자를 변환하고 이를 리스트에 저장하는 for문과 계산하는 for문을 각각 작성해서 풀었는데

사실 그럴 필요 없이 숫자를 변환한 뒤 바로 계산하면 되어서 코드를 개선했다.