티스토리 뷰
반응형
15829번: Hashing
APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정
www.acmicpc.net
풀이
상당히 특이한 문제이다. 경우에 따라 50점이 나올 수도 있는 문제이다.
50점이 나오는 경우에는 파이썬이 아닐 때는 int의 범위 문제이다. long long을 써서 해결해야 한다.
만약 python이라면 범위는 문제가 없다. 정확히는 너무 큰 수는 출력하는 데 힘들어서 50점을 주는 것이다.
따라서 나머지를 M(문제에서는 1234567891)으로 나눈 나머지로 출력해주면 된다.
L=int(input())
arr=str(input())
first=ord(arr[0:1])-96 #a를 처음에 정해준다.
for i in range(1,len(arr)):
al=ord(arr[i:i+1])-96
first+=al*(31**i)
print(first%1234567891)
수식에는 있고, 예제에는 없어서 떠올리기 힘든 나머지 연산이다.
그 이외에는 그냥 각각의 문자열을 받아서 ord로 숫자로 바꿔주면 되므로 아주 간단하다.
첫번째 알파벳을 처음에 정해주고, 그 뒤에 각각의 숫자를 변환하여 거기에 더해서 추가해준다.
i가 1부터 시작하는 이유는 당연히 첫번째 알파벳은 건너뛰어야 하기 떄문.
그렇게 나온 합을 M으로 나눠주면 간단하게 100점이 나온다.
나머지를 하느냐 하지 않느냐에 따라 50점이 갈리니 이 점을 주의하도록 하자.
반응형