[백준/BOJ] 20920번 영단어 암기는 괴로워 (C/C++)

백준 온라인 저지(BOJ) 20920번 영단어 암기는 괴로워

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

20920번: 영단어 암기는 괴로워

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

 

1. 문제

효율적인 영어 단어 암기를 위한 아래의 정렬 규칙에 따라 단어를 정렬한 후 순서대로 출력

1) 자주 나오는 단어 → 2) 길이가 긴 단어 → 3) 알파벳 순서

 

2. 풀이

Hash Table 자료 구조와 Merge Sort 정렬 알고리즘을 사용하여 풀었습니다.

 

단어가 나온 빈도수를 확인하기 위해서 단어를 key로 하는 Hash Table로 구현했고,

단어가 등장할 때마다 hash 탐색 후 없으면 추가해주고 hash의 value 중 하나인 cnt 값을 증가시켰습니다.

길이가 M 미만인 단어는 출력 대상이 아니므로 hash에 기록조차 하지 않습니다.

 

기록을 마친 후에는 기록이 된 hash 구조체들만 추려내어 하나의 배열로 정리합니다.

그리고 그 배열을 문제의 규칙에 따라 정렬한 뒤 순서대로 출력하면 됩니다.

 

 

hash 구조체를 추려내는 과정에서 메모리 사용을 최소화하기 위해

구조체 자체가 아닌 구조체의 주소값, 즉 포인터를 배열로 만들었습니다.

 

c언어에서 주소값은 크기가 4 byte 뿐이라 상대적으로 공간 효율이 좋아지는데,

정렬 시 swap을 할 때에도 값 하나만 바꾸면 되기 때문에 시간 효율까지 좋아집니다.

구조체를 활용한 정렬 문제에서는 포인터를 쓰지 않을 이유가 없으니 숙달한 후 자주 활용하기를 권장드립니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
20920_영단어 암기는 괴로워
5608KB	64ms
*/
#include <cstdio>

const int LM = 100000;
const int HLM = LM * 3 / 2;
const int CLM = 11;
int N, M, slen, wCnt;
char s[CLM];

struct _hash {
	char key[CLM];
	int cnt;
	int len;
} HASH[HLM];
_hash *a[LM], *t[LM];

int strlen(const char *a) {
	int len = 0;
	while (*a++) ++len;
	return len;
}

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

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

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

int h_find(char *key) {
	int h = hash(key);
	int cnt = HLM;
	while (HASH[h].key[0] && cnt--) {
		if (!strcmp(HASH[h].key, key)) return h;
		h = (h + 1) % HLM;
	}
	return h;
}

int hashcmp(_hash *a, _hash *b) {
	if (a->cnt != b->cnt) return b->cnt - a->cnt;
	if (a->len != b->len) return b->len - a->len;
	return strcmp(a->key, b->key);
}

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 (hashcmp(a[i], a[j]) < 0) t[k++] = a[i++];
		else t[k++] = a[j++];
	}

	while (i <= m) t[k++] = a[i++];
	while (j <= e) t[k++] = a[j++];

	for (i = s; i <= e; ++i) a[i] = t[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", s);
		slen = strlen(s);
		if (slen < M) continue;

		int h = h_find(s);
		_hash *hash = &HASH[h];
		if (!hash->key[0]) {
			strcpy(s, hash->key);
			hash->len = slen;
		}
		++hash->cnt;
	}

	for (int i = 0; i < HLM; ++i) {
		if (!HASH[i].key[0]) continue;
		a[wCnt++] = &HASH[i];
	}

	mSort(0, wCnt - 1);
	for (int i = 0; i < wCnt; ++i) printf("%s\n", a[i]->key);

	return 0;
}