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

백준 온라인 저지(BOJ) 7785번 회사에 있는 사람
https://www.acmicpc.net/problem/7785

7785번: 회사에 있는 사람

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

1. 문제

각 직원들의 출퇴근 기록을 순차적으로 반영한 후
현재 회사에 있는 사람을 알파벳 역순으로 출력

 

2. 풀이

코드의 큰 틀은 ① hash 자료구조 + ② merge sort입니다.
 
직원 이름을 hash 값으로 mapping하여 hash table에 기록 및 삭제했고
출퇴근 기록을 모두 확인한 후에는 hash table에 남은 직원만 정렬하여 출력했습니다.
 

1) hash 자료구조

직원이 출근하면(enter) hash table에 이름을 저장하고,
퇴근하면(leave) 해당 hash 값을 찾아가 이름을 지웠습니다.
 
hash는 통상 key, value 값이 둘 다 필요하기 때문에 struct로 구현하는데
이 문제는 name(key)만으로 충분히 처리가 가능해서 굳이 struct 구현은 하지 않았습니다.
 
hash 충돌은 open addressing으로 해결했습니다.
따라서 직원이 퇴근하더라도 hash table에서 값을 아예 지울 수는 없습니다.

다만 충돌이 발생하는 hash key에서 시간/공간 낭비가 생길 수 있기 때문에
이를 방지하기 위해 삭제 시 name의 0번째 값(name[0])을 -1(DELETED)로 변경했습니다.
 
이후 add 시에는 name[0]이 0이거나 -1인 자리를 찾아 기록하면 되고
delete 시에는 name[0]이 0이 아닌 값에서 이름을 찾아가면 됩니다.
(-1에서 탐색을 마치지 않게 됨)
 

2) merge sort

저장/삭제가 완료된 hash table을 full scan하면서 name[0] > 0 인 이름을 새로운 배열에 저장합니다.
그리고 해당 배열을 역순 정렬(merge sort)한 후 출력하면 됩니다.
 
배열에 문자열을 그대로 저장하면 배열에 저장하거나 정렬하는 시점에
문자열 전체를 계속 복사하기 때문에 시간/공간 낭비가 발생합니다.

이를 방지하기 위해 문자열(char 배열)이 아닌 char pointer를 저장하게 했습니다.
 
각 pointer에는 직원 이름의 첫 번째 char 문자가 저장된 주소를 저장하는데,
이 값을 문자열로 처리하면 이후 공백('\0')이 나타날 때 까지 하나의 문자열로 보기 때문에 문제없이 동작합니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
7785_회사에 있는 사람
28460KB	68ms
*/
#include <cstdio>

const int LM = 1000000;
const int HLM = LM * 2;
const int CLM = 6;
const int DELETED = -1;

char ht[HLM][CLM], name[CLM], log[CLM];
char* a[LM], * t[LM];
int N;

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;
}

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

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

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

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

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(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", &N);

	for (int i = 0; i < N; ++i) {
		scanf("%s %s", name, log);
		if (log[0] == 'e') h_add(name);
		else h_delete(name);
	}

	int idx = 0;
	for (int i = 0; i < HLM; ++i) {
		if (ht[i][0] > 0)
			a[idx++] = ht[i];
	}
	
	mSort(0, idx - 1);

	for (int i = 0; i < idx; ++i) printf("%s\n", a[i]);
	return 0;
}