[백준/BOJ] 1764번 듣보잡 (C/C++)

백준 온라인 저지(BOJ) 1764번 듣보잡

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

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

 

1. 문제

듣도 못한 사람 N명, 보도 못한 사람 M명이 주어졌을 때

듣도 보도 못한 사람(듣보잡)의 수와 그 명단을 사전순으로 출력

 

2. 풀이

hash table과 merge sort 로 구현하여 풀었습니다.

이 문제에서는 hash table에 입력한 data를 지우는 등의 복잡한 처리가 없기 때문에

find(key에 해당되는 h 찾기) 함수만 구현하고 main에서 처리했습니다. 

 

일반적인 find 함수와는 다르게 값을 찾지 못한 경우에도 해당 h를 return 하게 했고,

main 함수에서 해당 hash table에 이름이 있는지 확인하여 기록하는 형태입니다.

 

 

단계 별로 풀어보기를 순서대로 진행하고 계신다면,

hash 구조는 몇 차례 중복해서 푼 상태일 것 같으니 추가 설명없이 코드로 풀이를 대체하겠습니다.

 

아래 예시는 find 대신 add와 delete를 구현한 hash table 문제 예시입니다.

https://rightbellboy.tistory.com/257

[백준/BOJ] 7785번 회사에 있는 사람 (C/C++)

 

hash table은 문제에 따라 다양한 형태로 응용이 가능하니

자유자재로 활용할 수 있도록 여러 문제를 풀어보시면 좋을 것 같습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1764_듣보잡
40176KB	60ms
*/
#include <cstdio>

const int CLM = 21;
const int LM = 500000;
const int HLM = LM * 2;

char input[CLM];
int N, M, cnt;

struct _ht {
	char name[CLM];
	int flag[2];
} HT[HLM];

_ht* res[LM], * tmp[LM];

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

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

int hash(const char* s) {
	unsigned long hash = 5381;
	int c;
	while (c = *s++) hash = (((hash << 5) + hash) + c) % HLM;
	return hash % HLM;
}

int h_find(const char* s) {
	int h = hash(s);
	int cnt = HLM;
	while (HT[h].name[0] && cnt--) {
		if (!my_strcmp(s, HT[h].name)) break;
		h = (h + 1) % HLM;
	}
	return h;
}

void mSort(int s, int e) {
	if (s >= e) return;

	int m = (s + e) / 2;
	mSort(s, m);
	mSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (my_strcmp(res[i]->name, res[j]->name) < 0) tmp[k++] = res[i++];
		else tmp[k++] = res[j++];
	}
	while (i <= m) tmp[k++] = res[i++];
	while (j <= e) tmp[k++] = res[j++];

	for (i = s; i <= e; ++i) res[i] = tmp[i];
}

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", input);
		int h = h_find(input);
		my_strcpy(input, HT[h].name);
		HT[h].flag[0] = 1;
	}

	for (int i = 0; i < M; ++i) {
		scanf("%s", input);
		int h = h_find(input);
		if (!HT[h].name[0]) my_strcpy(input, HT[h].name);
		HT[h].flag[1] = 1;
	}

	for (int i = 0; i < HLM; ++i) {
		if (HT[i].flag[0] && HT[i].flag[1]) res[cnt++] = &HT[i];
	}

	mSort(0, cnt - 1);

	printf("%d\n", cnt);
	for (int i = 0; i < cnt; ++i) printf("%s\n", res[i]->name);

	return 0;
}