문제 URL:
https://www.acmicpc.net/problem/15829
15829번: Hashing
APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정
www.acmicpc.net
다음 문제는 문제에서 주어진 해시함수와 입력 문자열을 사용해 해시 값을 계산하여 정수로 출력하는 문제로,
해싱 기법을 이용한 문제이다.
이 문제는 이전에 본 문제들과 다르게 문제 채점이 50점과 100점으로 나뉘는데
제출한 내 코드는 50점을 받아서 100점은 어떻게 받는지 구글링해 보았다.
50점짜리와 100점짜리 코드의 기본적인 원리는 같지만 100점짜리 코드는
아래 두 코드가 같다는 원리가 적용된다.
int result1 = (a * b) % c; // 코드1
int result2 = (a % c) * (b % c); // 코드2
if(result2 > c)
result2 = result2 % c;
코드1 대신 코드2를 사용하면 정답의 크기가 줄어든다는 장점이 있다.
아래는 각각 50점짜리 코드와 100점짜리 코드이다.
// 50점짜리 코드
#include <iostream>
#include <string>
using namespace std;
#define M 1234567891
#define R 31
long long L;
long long answer = 0;
string alphabets;
int main() {
cin >> L;
cin >> alphabets;
for (int i = 0; i < L; i++) {
char alphabet = alphabets[i] - 'a' + 1; // 알파벳 한 글자 저장
long long r = 1;
for (int j = 1; j <= i; j++) { // r의 지수만큼 31 곱하기
r *= R;
}
answer += (long long)alphabet * r;
}
cout << answer;
}
// 100점짜리 코드
#include <iostream>
#include <string>
using namespace std;
#define M 1234567891
#define R 31
long long L;
long long answer = 0;
string alphabets;
int main() {
cin >> L;
cin >> alphabets;
for (int i = 0; i < L; i++) {
char alphabet = alphabets[i] - 'a' + 1; // 알파벳 한 글자 저장
long long r = 1;
for (int j = 1; j <= i; j++) { // r의 지수만큼 31 곱하기
r *= R;
// ***추가된 코드***
if (r > M)
r = r % M;
}
answer += (long long)alphabet * r;
// ***추가된 코드***
if (answer > M)
answer = answer % M;
}
cout << answer;
}