글 읽기 - 해시 관련 질문

lllllllllllllllllll 4년 전 0

제가 단일해시로 문제에 접근을 했는데, MOD값을 655731과 같은 큰 수를 주면 통과를 하고, 173, 6173과 같은 비교적 작은 소수를 주면 통과하지 못합니다.

사실 운으로 통과했다고 밖에 생각이 들지 않아서.. 혹시 데이터 사이즈에 따라 MOD값을 주는 기준이 있을까요?

아니면 저의 코드에 문제가 있어서 그런걸까요? 고수님들 지식 조금만 나눠주시면 감사드리겠습니다.

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int T, MOD = 655731;
vector<string> v[655731], input;

int h(string key)
{
	int x = 0, MUL = 1;
	for (int i = 0; key[i]; i++)
	{
		x = ((key[i] * MUL) + x) % MOD;
		MUL *= 7;
	}

	if (x < 0)
		x = -x;

	return x % MOD;
}
int main(void)
{
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		while (1)
		{
			string temp;
			cin >> temp;
			input.push_back(temp);
			if (temp == "say?")
				break;
		}

		for (int i = 0; input[i + 1] != "goes"; i++)
			v[h(input[i])].push_back(input[i]);

		int sz = input.size();
		for (int i = 0; i < sz; i++)
			if (input[i] == "goes")
			{
				int idx = h(input[i + 1]);
				int s = v[idx].size();
				vector<string> tempv;
				for (int j = 0; j < s; j++)
					if (v[idx][j] != input[i + 1])
						tempv.push_back(v[idx][j]);

				v[idx].clear();
				v[idx] = tempv;
			}

		for (int i = 0; input[i + 1] != "goes"; i++)
		{
			int idx = h(input[i]);
			//cout << input[i] << endl;
			if (!v[idx].empty())
				cout << input[i] << " ";

		}
		cout << endl;

		for (int i = 0; i < MOD; i++)
			v[i].clear();

		input.clear();
		
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

해시 관련 질문

lllllllllllllllllll 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말