BOJ 백준 1920 : 수 찾기

시작하면서

　이번 문제는 해시 테이블(Hash Table) 문제이다. 해시 테이블을 직접 구현해서 풀기 위해 그에 걸맞는 문제를 선정했다. 문제 분류는 이분 탐색으로 되어 있지만 해시 테이블을 사용해도 문제 해결이 가능하다.

BOJ 1920 - 수 찾기

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 4가지이다.

• N : 입력할 정수의 개수
• A[] : 입력되는 정수
• M : 존재하는지 알아봐야할 정수의 개수

​

문제 아이디어

　N과 M의 최대값이 10만이다. 입력하는 정수 A[] 들은 저장이 필요하고, 존재해야하는지 알아보아야 할 정수들은 저장할 필요가 없다. 숫자가 들어있는지, 없는지만 보면 되기 때문에 해시 테이블을 만들어서 바로바로 찾는 방법을 택한다.

​ 주의해야 할 점은 정수의 범위가 -2^31부터 이므로 음수가 배열 인덱스에 들어가지 않게 가중치를 더해주는 것이다.

​

해결

#include <iostream>
#include <list>

using namespace std;

#define HASH_TABLE_SIZE (1000)

typedef struct _HashValue
{
	int key;
	int value;
}HashValue;

/*
	파생된 객체에 대해서 생성/소멸은 허용
	복사는 방지
*/
class Uncopyable
{
protected:
	Uncopyable() { }
	~Uncopyable() { }
private:
	Uncopyable(const Uncopyable&);
	Uncopyable& operator=(const Uncopyable&);
};

/*
	HashTable Class
*/
class HashTable : Uncopyable
{
private:
	list<HashValue> m_HashTable[HASH_TABLE_SIZE];
	int m_nHashTableValueCount;

private:
	int GetHash(const int key);
	bool IncreaseValueCount();
	bool DecreaseValueCount();

public:
	HashTable()
	{
		this->m_nHashTableValueCount = 0;
	}
	~HashTable()
	{
		this->m_nHashTableValueCount = 0;
	}

	bool InsertValue(const HashValue& hashValue);
	bool DeleteValue(const HashValue& hashValue);
	bool FindValue(const HashValue& hashValue);
	bool FindValue(const HashValue& hashValue, list<HashValue>::iterator& outIter);
};

int HashTable::GetHash(const int key)
{
	int hash = 0;

	hash = key - (HASH_TABLE_SIZE * (int)(key / HASH_TABLE_SIZE));

	if (hash < 0)
	{
		hash *= -1;
	}

	return hash;
}

bool HashTable::IncreaseValueCount()
{
	if (this->m_nHashTableValueCount < 0)
		return false;

	this->m_nHashTableValueCount++;

	return true;
}

bool HashTable::DecreaseValueCount()
{
	if (this->m_nHashTableValueCount < 0)
		return false;

	this->m_nHashTableValueCount--;

	return true;
}

bool HashTable::InsertValue(const HashValue& hashValue)
{
	int hash = 0;
	hash = this->GetHash(hashValue.key);

	this->m_HashTable[hash].push_front(hashValue);
	this->IncreaseValueCount();

	return true;
}

bool HashTable::DeleteValue(const HashValue& hashValue)
{
	list<HashValue>::iterator iter;

	if (this->FindValue(hashValue, iter) == false)
		return false;

	int hash = 0;
	hash = this->GetHash(hashValue.key);

	this->m_HashTable[hash].erase(iter);
	this->DecreaseValueCount();

	return true;
}

bool HashTable::FindValue(const HashValue& hashValue)
{
	list<HashValue>::iterator iter;
	int hash = 0;
	hash = this->GetHash(hashValue.key);

	for (iter = this->m_HashTable[hash].begin(); iter != this->m_HashTable[hash].end(); iter++)
	{
		if (iter->key == hashValue.key)
			break;
	}

	if (iter != this->m_HashTable[hash].end())
		return true;
	else
		return false;
}

bool HashTable::FindValue(const HashValue& hashValue, list<HashValue>::iterator& outIter)
{
	list<HashValue>::iterator iter;
	int hash = 0;
	hash = this->GetHash(hashValue.key);

	for (iter = this->m_HashTable[hash].begin(); iter != this->m_HashTable[hash].end(); iter++)
	{
		if (iter->key == hashValue.key)
		{
			outIter = iter;
			break;
		}
	}

	if (iter != this->m_HashTable[hash].end())
		return true;
	else
		return false;
}

/*
	MAIN FUNCTION
*/
int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// ----------

	HashTable hashTable;
	HashValue hashValue;
	int N, M, input;


	/*
		FIRST INPUT
	*/
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> hashValue.key;

		hashValue.value = hashValue.key;

		hashTable.InsertValue(hashValue);
	}
	
	/*
		SECOND INPUT
	*/
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> hashValue.key;

		hashValue.value = hashValue.key;

		if (hashTable.FindValue(hashValue) == true)
		{
			cout << "1\n";
		}
		else
		{
			cout << "0\n";
		}
	}

	return 0;
}

​

마치며

　이전에도 해시 테이블은 여러번 만들어보아서 어렵지 않았다. 그래서 굳이 필요하지는 않지만 클래스 구조로 코드를 짜보았다.

​ 해시 테이블을 만들면서 항상 느끼는 부분은 각 문제에 따라 해시 값을 만드는 함수를 어떻게 짜느냐가 굉장히 중요할 것이고, 이러한 문제를 실전에서 직면했을 때 내가 적절한 해시 함수를 만들 수 있을지에 대한 궁금증이 있다. 부디 실전에서 만났을 때 잘 해결할 수 있는 실력을 갖추고 있기를 바란다.