BOJ 1764 : 듣보잡 (vector, sort)

삼성 B형 전체 링크

 

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

 

 

Hash/Merge를 이용했던 듣보잡 문제를 vector, algorithm(sort)를 이용해서 풀어보자.

 

vector를 이용해 메모리 풀을 대체할 수 있다.

/* before */

typedef struct st
{
	char name[21];
	struct st *next;
}HASH;

HASH Hash[MAX_TABLE];
HASH POOL[500000 + 50000];
int pcnt;

 

아래와 같이 필요한 만큼의 배열로 선언하면 된다.

/* after */

vector<string> Hash[MAX_TABLE];

 

이 문제는 tc가 단독이지만, 실제 B형에서는 아래의 코드로 초기화해야 할 수도 있다.

/* tc가 여러 개인 경우는 init 코드 추가 */
for (int i = 0; i < MAX_TABLE; i++) Hash[i].clear();

---

main에서 입력은 아래와 같이 링크드 리스트를 연결했다.

/* before */

for (int i = 0; i < N;i++)
{
	scanf("%s", str);
	ull h = hash(str);

	nd = &POOL[pcnt++];
	mystrcpy(nd->name, str);

	nd->next = Hash[h].next;
	Hash[h].next = nd;
}

 

이제 vector에 push_back으로 변경하면 된다.

이때, 함수명 hash → getHash로 변경하였다. (선언한 헤더에 의해 hash가 모호하다는 경고가 나타난다.)

/* after */

for (int i = 0; i < N; i++)
{
	scanf("%s", str);
	ull h = getHash(str);

	Hash[h].push_back(str);
}

 

hash에 대해 듣보잡 리스트를 순회할 때도 링크드 리스트와, mystrcmp를 사용하였다.

/* before */

for (int i = 0; i < M;i++)
{
	scanf("%s", str);
	ull h = hash(str);

	for (nd = Hash[h].next; nd; nd = nd->next)
	{
		if (!mystrcmp(nd->name, str))
			DBJ_List[listcnt++] = nd->name;
	}
}

 

string은 == 비교가 가능하기 때문에 아래와 같이 수정하면 된다.

/* after */

for (int i = 0; i < M; i++)
{
	scanf("%s", str);
	ull h = getHash(str);

	int size = Hash[h].size();

	string st = str;
	for (int i = 0; i < size; i++)
	{
		if (Hash[h][i] == st)
			DBJ_List[listcnt++] = st;
	}
}

 

마지막으로 merge sort의 sort는 algorithm의 sort로 대체 가능하다.

시작점, 시작점 + 정렬할 크기 를 넣어주면 정렬된다.

sort(DBJ_List, DBJ_List + listcnt);

 

string의 기본 sort가 사전순으로 정렬이다.

만약 역 사전순으로 정렬하고 싶다면 compare 함수를 만들어서 비교 함수를 추가하면 된다.

bool comp(string a, string b)
{
	if (a > b) return true; /* 역 사전순 */
	return false;
}

int main()
{
	...
    
	sort(DBJ_List, DBJ_List + listcnt, comp);

	...
}
	

 

마지막으로 string의 출력은 c_str()을 이용하면 된다.

for (int i = 0; i < listcnt; i++) printf("%s\n", DBJ_List[i].c_str());

 

최종 코드는 아래와 같다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define MAX_TABLE (1000007)

typedef unsigned long long int ull;
int N, M;

vector<string> Hash[MAX_TABLE];

ull getHash(const char *str)
{
	ull hash = 5381;
	int c;

	while (c = *str++)
	{
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}

	return hash % MAX_TABLE;
}

string DBJ_List[500000 + 5000]; /* 듣보잡 List */
int listcnt = 0;

int main(void)
{
	char str[21];

	scanf("%d %d", &N, &M);

	/* tc가 여러 개인 경우는 init 코드 추가 */
	//for (int i = 0; i < MAX_TABLE; i++) Hash[i].clear();

	for (int i = 0; i < N; i++)
	{
		scanf("%s", str);
		ull h = getHash(str);

		Hash[h].push_back(str);
	}

	for (int i = 0; i < M; i++)
	{
		scanf("%s", str);
		ull h = getHash(str);

		int size = Hash[h].size();

		string st = str;
		for (int i = 0; i < size; i++)
		{
			if (Hash[h][i] == st)
				DBJ_List[listcnt++] = st;
		}
	}

	sort(DBJ_List, DBJ_List + listcnt);

	printf("%d\n", listcnt);
	for (int i = 0; i < listcnt; i++) printf("%s\n", DBJ_List[i].c_str());

	return 0;
}