[백준/BOJ] 25192번 인사성 밝은 곰곰이 (C/C++)

백준 온라인 저지(BOJ) 25192번 인사성 밝은 곰곰이

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

25192번: 인사성 밝은 곰곰이

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

 

1. 문제

ENTER(새로운 사람 입장) 혹은 채팅을 입력한 유저의 닉네임이 입력으로 주어짐

새로운 사람 입장 후 각 유저의 첫 채팅은 반드시 곰곰티콘을 사용한 인사이고, 이후는 채팅은 평범한 채팅임

전체 기록 중 곰곰티콘이 사용된 횟수를 출력

 

2. 풀이

hash table 구조를 활용하여 각 채팅마다 O(1)의 시간복잡도를 가지도록 구현해서 풀었습니다.

우선 hash의 key는 유저의 닉네임으로, 입력으로 받을 때마다 탐색한 후 없으면 해당 자리에 기록합니다.

 

hash의 value는 enter가 등장한 횟수입니다.

우선 ENTER가 주어지면 enter_cnt라는 global 변수를 1 증가시킵니다.

 

그리고 유저 닉네임이 주어질 때 마다 해당 유저의 hash의 value가 enter_cnt와 같은지 확인합니다.

만약 같다면 이미 채팅을 한(곰곰티콘을 사용한) 유저이므로 넘어가고,

다르면 hash의 value를 enter_cnt로 변경해준 뒤 출력할 res 값을 1 증가시킵니다.

 

 

추가로 hash 충돌은 open addressing 방식을 활용하여 해결했습니다.

따라서 hash table의 크기를 주어지는 유저 수의 최대값(10만)의 1.5배로 구현했습니다.

(통상 2~3배가 일반적이나 크기를 줄이며 수차례 제출해본 결과 15만까지 코드의 최대 속도인 44ms가 나옴)

 

그 외 부분은 아래 코드로 설명 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
25192_인사성 밝은 곰곰이
6584KB	44ms // HLM = 200000
5126KB	44ms // HLM = 150000 <-
3848KB	112ms // HLM = 100000
*/
#include <cstdio>

const int HLM = 150000;
const int CLM = 21;
int N, enter_cnt, res;
char input[CLM], enter[CLM] = "ENTER";

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

struct _hash {
	char key[CLM];
	int value;
} HASH[HLM];

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(key, HASH[h].key)) return h;
		h = (h + 1) % HLM;
	}
	return h;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	while (N--) {
		scanf("%s", input);
		if (!strcmp(input, enter)) ++enter_cnt;
		else {
			int h = h_find(input);
			if (!HASH[h].key[0]) strcpy(input, HASH[h].key);

			if (HASH[h].value != enter_cnt) {
				HASH[h].value = enter_cnt;
				++res;
			}
		}
	}

	printf("%d\n", res);
	return 0;
}