[백준/BOJ] 26069번 붙임성 좋은 총총이 (C/C++)

백준 온라인 저지(BOJ) 26069번 붙임성 좋은 총총이

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

26069번: 붙임성 좋은 총총이

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

 

1. 문제

서로 다른 두 사람이 만난 기록이 시간 순서대로 N개 주어짐

무지개 댄스를 추지 않던 사람은 무지개 댄스를 추던 사람을 만나면 이후 계속 무지개 댄스를 춤

기록 시작 전 무지대 댄스를 추던 사람은 총총이("ChongChong") 뿐 일 때,

마지막 기록 후 무지개 댄스를 추고 있는 사람의 수를 출력

 

2. 풀이

Hash Table 자료구조를 통해 구현하였습니다.

hash의 value 값을 활용하여 춤을 추고 있는지 여부를 확인합니다. (1이면 추고 있는 것)

"ChongChong"이는 입력을 받기 전에 미리 Hash Table에 넣고 value 값을 1로 바꿔두었습니다.

 

N개의 입력은 한 줄 씩 처리했는데, 서로 다른 두 사람의 이름을 Table에서 찾고 없으면 기록했습니다.

그리고 두 사람 중 한 사람만 무지개 댄스를 추고 있으면 두 사람의 value 값을 1로 변경해주었습니다.

(정확히 구현하면 춤을 추지 않고 있던 사람만 변경하면 됩니다)

 

마지막에 Hash Table의 모든 value 값을 더해서 출력하면 됩니다.

저는 이 과정에서 O(n)의 시간 복잡도를 쓰게 되는 것이 마음에 들지 않아서

사람들이 춤을 출 때마다 cnt 변수를 1씩 증가시켜서 마지막에 그대로 출력했습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
26069_붙임성 좋은 총총이
1168KB	0ms
*/
#include <cstdio>

const int HLM = 2000;
const int CLM = 21;
int N, cnt;
char A[CLM], B[CLM];

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
	char cc[11] = "ChongChong";
	int h = h_find(cc);
	strcpy(cc, HASH[h].key);
	HASH[h].value = 1;
	++cnt;

	scanf("%d", &N);
	while (N--) {
		scanf("%s %s", A, B);
		int ha = h_find(A);
		int hb = h_find(B);

		if (!HASH[ha].key[0]) strcpy(A, HASH[ha].key);
		if (!HASH[hb].key[0]) strcpy(B, HASH[hb].key);

		if (HASH[ha].value ^ HASH[hb].value) {
			HASH[ha].value = HASH[hb].value = 1;
			++cnt;
		}
	}

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

* 두 사람 중 한 사람만 춤을 출 때 변경점이 생기므로 ^(XOR) 연산자를 활용하여 처리했습니다.