[BOJ] 백준 14425 문자열 집합

Approach

출처: https://www.acmicpc.net/problem/14425

 

집합 S에 같은 문자열은 주어지지 않는다.

이에 대한 구현은 할 필요가 없다.

 

처음 주어지는 N개의 문자로 Hash Table을 구성한다.

다음 M개의 문자열을 입력받을 때

Hash Table에 해당 문자열이 존재하는 확인한다.

📌 [C++] [STL] Set

[C++] [STL] Set

 

 

Hash Table을 구현한다는 것에서

조건이 까다롭지 않기 때문에

기초문제가 될 수 있는 문제이다.

STL을 이용해도 좋지만 직접 구현해보아도 좋을 것 같다.

📌 [해시] Hash란?

[해시] Hash란?

 

 

STL

#include <iostream>
#include <string>
#include <set>

using namespace std;

int N, M, answer;
string word;
set<string> hTbl;

int main()
{
    // freopen("input.txt", "r", stdin);

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> word;
        hTbl.insert(word);
    }

    for (int i = 0; i < M; i++) {
        cin >> word;
        if (hTbl.find(word) != hTbl.end())
            answer++;
    }

    cout << answer << endl;;
}

 

직접 구현

#include <stdio.h>

void _strcpy(char* dest, const char* src) {
	while (*dest++ = *src++);
}

int _strcmp(const char* s, const char* t) {
	while (*s && *s == *t) s++, t++;
	return *s - *t;
}

const int MAX_N = 1e4 + 5;
const int MAX_LEN = 500 + 5;
const int SIZE = 1 << 15;
int N, M, answer;
char str[MAX_LEN];
int djb2(char* s) {
	int hash = 5381;
	for (; *s; ++s)
		hash = hash * 33 + *s;
	return (hash % SIZE) < 0 ? (hash % SIZE) * (-1) : (hash % SIZE);
}

struct Node {
	char str[MAX_LEN];
	Node *prev, *next;

	Node* alloc(char _str[], Node* _prev, Node* _next) {
		_strcpy(str, _str);
		prev = _prev, next = _next;
		if (next) next->prev = this;
		if (prev) prev->next = this;
		return this;
	}
	void pop() {
		if (next) next->prev = prev;
		if (prev) prev->next = next;
	}
}buf[MAX_N], head[SIZE], tail[SIZE];
int bcnt;

void init()
{
	bcnt = 0;
	for (int i = 0; i < SIZE; ++i) 
	{
		head[i].next = &tail[i];
		tail[i].prev = &head[i];
	}
}

bool probing(char str[]) 
{
	int key = djb2(str);
	Node* p = head[key].next;
	for (; p; p = p->next) 
	{
		if (_strcmp(p->str, str) == 0) 
		{
			return true;
		}
	}
	return false;
}

int main() 
{
	// freopen("input.txt", "r", stdin);
	init();

	// N개 만큼 입력받아 문자열 Hash Table 구축
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; ++i) 
	{
		scanf("%s", str);
		int key = djb2(str);
		Node* p = buf[bcnt++].alloc(str, &head[key], head[key].next);
	}


	// M개 만큼 문자열을 입력받아서
	// Hash Table에 존재하는지 확인
	for (int i = 0; i < M; ++i)
	{
		scanf("%s", str);
		if (probing(str)) answer++;
	}

	printf("%d\n", answer);
}