[백준] 15829 Hashing (C++)

 

문제 URL:

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

15829번: Hashing

 

다음 문제는 문제에서 주어진 해시함수와 입력 문자열을 사용해 해시 값을 계산하여 정수로 출력하는 문제로,

해싱 기법을 이용한 문제이다.

 

이 문제는 이전에 본 문제들과 다르게 문제 채점이 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;
}

 

참조: https://42kchoi.tistory.com/m/277