[백준/BOJ] 14425번 문자열 집합 (C/C++)

백준 온라인 저지(BOJ) 14425번 문자열 집합
https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

* 사용언어 : C언어, C++
 

1. 문제

숫자 N과 M, 그리고 이후 주어지는 N개의 문자열이 집합 S에 있다고 할 때
그 다음으로 주어지는 M개의 문자열 중에 몇 개가 집합 S에 포함되는지를 출력

 

2. 풀이

주어지는 N개의 문자열을 Hash Table 에 저장(add)하고,
이후 M개의 문자열은 Hash Table 을 탐색(find)해서 탐색된 개수를 출력하게 했습니다.
 
문제에서 집합 S에 같은 문자열이 여러 번 주어지는 경우가 없다고 했기 때문에
N개의 문자열에 중복이 없으므로 add 시 중복 처리는 구현하지 않았습니다.
 
M개의 문자열, 즉 find 시 중복에 대한 내용은 문제에 따로 명시되어 있지 않았습니다.
저는 일단 중복이 없다고 가정하고 풀어봤는데 정답이 되었습니다.
 
만약 중복이 있다면 Hash Table 을 struct 로 구현한 뒤
int isCheck 정도의 변수를 추가해주고 count 가 된 경우 1로 바꾸어 주면 될 것 같습니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
14425_문자열 집합
15792KB	176ms
*/
#include <cstdio>

const int CLM = 501;
const int HLM = 10000 * 3;
char ht[HLM][CLM], s[CLM];
int n, m, cnt;

int my_strcmp(const char *a, const char *b) {
	while (*a && *b && *a == *b) a++, b++;
	return *a - *b;
}

void my_strcpy(const char *src, char *des) {
	while (*src) *des++ = *src++;
	*des = 0;
}

int hash(const char *s) {
	unsigned long hash = 5381;
	int c;

	while (c = *s++) hash = (((hash << 5) + hash) + c) % HLM;
	return hash % HLM;
}

void add(const char *s) {
	int h = hash(s);

	while (ht[h][0]) h = (h + 1) % HLM;
	my_strcpy(s, ht[h]);
}

int find(const char *s) {
	int h = hash(s);
	int cnt = HLM;

	while (ht[h][0] && cnt--) {
		if (!my_strcmp(s, ht[h])) return 1;
		h = (h + 1) % HLM;
	}
	return 0;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; ++i) {
		scanf("%s", s);
		add(s);
	}

	for (int i = 0; i < m; ++i) {
		scanf("%s", s);
		cnt += find(s);
	}

	printf("%d\n", cnt);
	return 0;
}