[C++] 백준 15829번: Hashing

15829번: Hashing

1. Small (50점) 서브태스크

Small(50 점)에 대한 해답은 어렵지 않다.

각 문자에 대해서 int 형식으로 변환하여 31를 인덱스만큼 거듭제곱한 것을 곱하고 합한 값을 1234567891로 나눈 나머지를 출력하면 된다.

1 ≤ L ≤ 5일 때는 int로도 충분히 풀 수 있을 정도로 숫자가 크지 않다.

#include <cstdio>

using namespace std;

int pow(int num, int p) {
	int result = 1;
	for (int i = 0; i < p; i++) {
		result *= num;
	}
	return result;
}

int main() {
	int L;
	scanf("%d", &L);
	char* str = new char[L + 1];
	scanf("%s", str);
	int H = 0;
	for (int i = 0; i < L; i++) {
		int value = (str[i] - 96) * pow(31, i);
		H += value;
	}
	H %= 1234567891;
	printf("%d\n", H);
	delete[] str;
	return 0;
}

 

2. Large (100점) 서브태스크

하지만 Large(100점)의 경우는 큰 수 계산을 해야한다.

31의 49승은 무려 73자리나 되며, 이를 연산하는 것을 따로 구현해야 하는 것이다.

큰 수에 대한 곱셈과 나머지 연산을 구현해야 한다.

큰 수는 char 배열에 저장하기로 하고, 그 크기는 76이면 적당할 것이다.

왜냐하면 ∑ 26 * 31 ⁿ (from 0 to 49)의 결과 값이

320580266032658717156114439753831705658779984253920374290520601088075796800

와 같으며 75자리이기 때문이다.

내 답안은 다음과 같다.

#define MAX_DIGIT 75
#define R 26
#define M 1234567891
#define CH_M "1987654321"

#include <cstdio>

void multiply(char* lhs, int rhs) {
	int up = 0;
	for (int i = 0; i < MAX_DIGIT; i++) {
		if (lhs[i] == 0)
			if (up != 0)
				lhs[i] = '0';
			else break;
		int multiple = (lhs[i] - '0') * rhs + up;
		up = multiple / 10;
		lhs[i] = '0' + multiple % 10;
	}
}

void power(char* arr, int base, int exp) {
	arr[0] = '1';
	for (int i = 0; i < exp; i++)
		multiply(arr, base);
}

void add(char* lhs, char* rhs) {
	int up = 0;
	for (int i = 0; i < MAX_DIGIT; i++) {
		if (lhs[i] == 0 && rhs[i] == 0 && up == 0) break;
		if (lhs[i] == 0)
			lhs[i] = '0';
		if (rhs[i] == 0)
			rhs[i] = '0';
		int sum = (lhs[i] - '0') + (rhs[i] - '0') + up;
		up = sum / 10;
		lhs[i] = '0' + (sum % 10);
	}
}


bool compare(const char* lhs, const char* rhs) {
	int l_len = 0;
	for (int i = 0; lhs[i] != 0; i++)
		l_len++;
	int r_len = 0;
	for (int i = 0; rhs[i] != 0; i++)
		r_len++;
	if (l_len > r_len)
		return true;
	if (l_len < r_len)
		return false;

	for (int i = l_len; i >= 0; i--) {
		if (lhs[i] > rhs[i])
			return true;
		if (lhs[i] < rhs[i])
			return false;
	}
	return true;
}

void subtract(char* lhs, const char* rhs) {
	int up = 0;
	for (int i = 0; lhs[i] != 0; i++) {
		if (rhs[i] == 0) {
			lhs[i] -= up;
			break;
		}
		int sub = lhs[i] - rhs[i] - up;
		if (sub < 0) {
			up = 1;
			sub += 10;
		}
		else {
			up = 0;
		}
		lhs[i] = '0' + sub;
	}
	for (int i = MAX_DIGIT; lhs[i] == '0' || lhs[i] == 0; i--)
		lhs[i] = 0;
}

void mod(char* rem) {
	char* temp = new char[MAX_DIGIT + 1];
	int upper = 65;
	for (int i = 0; i < MAX_DIGIT + 1; i++) {
		if (i < upper)
			temp[i] = '0';
		else if (i < upper + 10)
			temp[i] = CH_M[i - upper];
		else
			temp[i] = 0;
	}

	while (compare(rem, CH_M)) {
		if (compare(temp, rem) && upper != 0) {
			upper--;
			int j = 0;
			for (int i = 0; i < MAX_DIGIT + 1; i++) {
				if (i < upper)
					temp[i] = '0';
				else if (i < upper + 10) {
					temp[i] = CH_M[j];
					j++;
				}
				else
					temp[i] = 0;
			}
		}
		else {
			subtract(rem, temp);
		}
	}
	delete[] temp;
}

void print(char* arr) {
	for (int i = MAX_DIGIT; i >= 0; i--)
		if (arr[i] != 0)
			printf("%c", arr[i]);
	printf("\n");
}

int main() {
	int L;
	scanf("%d", &L);
	char* str = new char[L + 1];
	scanf("%s", str);

	char H[MAX_DIGIT + 1];
	char temp[MAX_DIGIT + 1];
	for (int i = 0; i < MAX_DIGIT + 1; i++) {
		H[i] = 0;
		temp[i] = 0;
	}

	for (int i = 0; i < L; i++) {
		power(temp, 31, i);
		multiply(temp, str[i] - 96);
		add(H, temp);
		for (int i = 0; i < MAX_DIGIT + 1; i++)
			temp[i] = 0;
	}
	mod(H);
	print(H);

	delete[] str;
	return 0;
}

코드에 대한 설명은 생략.

왜냐면 이 문제는 큰 수 연산을 활용해 푸는게 아니다.

그냥 각 항마다 나머지연산한 결과를 합하면 되는 것이었다.

답안 제출 후의 이 허무함이란...

이 코드를 짜는데 하루종일 걸렸다.