BOJ 7785 : 회사에 있는 사람 (vector)

삼성 B형 전체 링크

 

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

 

Hash Table + Merge Sort로 풀었던 회사에 있는 사람을 vector, string을 이용해서 풀어보자.

 

아래의 코드는 vector로 대체 가능하다. 

/* before */

typedef struct st
{
	char name[6];
	int in;
}DB;

DB dbList[1001000];    /* 전체 사람을 관리하는 list */
DB enterList[1001000]; /* 회사에 남은 사람을 저장할 list */

typedef struct st2
{
	DB *db;
	struct st2 *next;
}HASH;

HASH Hash[MAX_TABLE];
HASH POOL[MAX_TABLE];
int pcnt;

 

추가로 char name[6]는 string으로 바꾼다.

/* after */

typedef struct st
{
	string name;
	int in;
}DB;

DB dbList[1001000];    /* 전체 사람을 관리하는 list */
DB enterList[1001000]; /* 회사에 남은 사람을 저장할 list */

vector<DB*> Hash[MAX_TABLE];

---

enter 처리 부분의 cmd, name등은 string으로 교체한다.

/* before */

if (!mystrcmp(cmd, (char*)"enter")) /* enter 입력 */
{
	mystrcpy(dbList[count].name, name); /* DB에 순서대로 저장 */
	dbList[count].in = 1; /* in = 1 표시 */

	ull h = hash(name);

	HASH *nd = &POOL[pcnt++]; /* 해시 테이블에 연결 */
	nd->db = &dbList[count];

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

	count++;
}
else /* leave 입력 */
{ ... }

 

링크드 리스트 부분은 push_back으로 바꾸면 된다.

그리고 함수명 hash는 getHash로 변경한다. (모호한 표현 에러 발생)

/* after */

cin >> name >> cmd;

if (cmd == "enter") /* enter 입력 */
{
	dbList[count].name = name; /* DB에 순서대로 저장 */
	dbList[count].in = 1; /* in = 1 표시 */

	ull h = getHash(name.c_str());

	Hash[h].push_back(&dbList[count]);

	count++;
}
else /* leave 입력 */
{ ... }

 

leave에 대한 처리는 vector를 순회하면 된다.

else /* leave 입력 */
{
	ull h = getHash(name.c_str());

	int size = Hash[h].size();
	for (int i = 0; i < size; i++)
	{
		if (Hash[h][i]->name == name && Hash[h][i]->in)
		{
			Hash[h][i]->in = 0; /* in = 0 으로 변경 */
			break;              /* 동명이인이 없으므로 종료 */
		}
	}
}

 

마지막으로 sorting 부분에서 merge sort를 지우고 algorithm의 sort를 사용하도록 바꿨다.

sort는 기본 사전 순 출력이지만, 문제에서 역순을 원하기 때문에 compare를 새로 정의하였다.

bool compare(DB a, DB b)
{
	if (a.name > b.name) return true;
	return false;
}

int main()
{
	...
    
	inCnt = 0;
	for (int i = 0; i < count; i++)
		if (dbList[i].in) enterList[inCnt++] = dbList[i];

	sort(enterList, enterList + inCnt, compare);

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

	return 0;
}

 

최종 코드는 아래와 같다.

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

using namespace std;

#define MAX_TABLE (1000003)
typedef unsigned long long int ull;

int N;

typedef struct st
{
	string name;
	int in;
}DB;

DB dbList[1001000];    /* 전체 사람을 관리하는 list */
DB enterList[1001000]; /* 회사에 남은 사람을 저장할 list */

vector<DB*> 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;
}

bool compare(DB a, DB b)
{
	if (a.name > b.name) return true;
	return false;
}

int main()
{
	int count, inCnt;
	string name, cmd;

	scanf("%d", &N);

	/* 필요하면 초기화 */
	//for (int i = 0; i < MAX_TABLE; i++) Hash[i].clear();

	count = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> name >> cmd;

		if (cmd == "enter") /* enter 입력 */
		{
			dbList[count].name = name; /* DB에 순서대로 저장 */
			dbList[count].in = 1; /* in = 1 표시 */

			ull h = getHash(name.c_str());

			Hash[h].push_back(&dbList[count]);

			count++;
		}
		else /* leave 입력 */
		{
			ull h = getHash(name.c_str());

			int size = Hash[h].size();
			for (int i = 0; i < size; i++)
			{
				if (Hash[h][i]->name == name && Hash[h][i]->in)
				{
					Hash[h][i]->in = 0; /* in = 0 으로 변경 */
					break;              /* 동명이인이 없으므로 종료 */
				}
			}
		}
	}

	inCnt = 0;
	for (int i = 0; i < count; i++)
		if (dbList[i].in) enterList[inCnt++] = dbList[i];

	sort(enterList, enterList + inCnt, compare);

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

	return 0;
}

---

vector에서 erase로 불 필요한 원소를 삭제하는 코드는 링크를 참고하자.

 

이 문제는 map을 이용하면 더 쉽게 풀 수 있다.