[백준/BOJ] 1269번 대칭 차집합 (C/C++)

백준 온라인 저지(BOJ) 1269번 대칭 차집합

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

1269번: 대칭 차집합

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

 

1. 문제

자연수를 원소로 갖는 두 집합 A, B가 주어졌을 때

두 집합의 대칭 차집합의 원소의 개수를 출력(두 집합 A, B의 대칭 차집합은 (A-B)와 (B-A)의 합집합)

 

2. 풀이

hash table에 key(집합에 있는 원소)와 value(몇 번 등장했는지)를 기록했습니다.

value 값은 특별하게 중복 처리를 하지는 않고, 단순히 해당 숫자가 등장할 때 마다 +1 해주었습니다.

왜냐하면 집합의 정의에 따라 애초에 개별 집합에는 중복이 있을 수 없기 때문입니다.

 

입력을 받으면서 두 집합의 원소들을 연달아서 hash table에 기록했고,

이 후에 hash table을 순회하면서 value가 1인 경우 cnt를 1 증가시켰습니다.

 

hash table로 푸는 문제 중 상대적으로 단순한 문제라서 풀이는 이정도로 마치겠습니다.

 

 

추가로,

맨 처음에 100,000,000 크기의 int 배열을 생성해서 문제를 효율적으로 풀고자 했었는데

메모리 초과가 나서 hash table로 구현하여 풀었습니다.

크기가 1억인 int 배열의 크기는 4억 byte(약 381MB)가 되어 제한인 256MB를 넘게 됩니다.

4억 byte == 약 381 MB

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1269_대칭 차집합
10488KB	112ms
*/
#include <cstdio>

const int LM = 200000 * 2;
const int HLM = LM * 2;
int a[HLM], N, M, input, cnt;

struct _ht {
	int key;
	int value; // 0: empty, 1: target, 2: intersection
} HT[HLM];

int find(int key) {
	int h = key % HLM;
	int c = HLM;
	while (HT[h].key && c--) {
		if (key == HT[h].key) break;
		h = (h + 1) % HLM;
	}
	return h;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N + M; ++i) {
		scanf("%d ", &input);
		int h = find(input);
		if (!HT[h].key) HT[h].key = input;
		++HT[h].value;
	}

	for (int i = 0; i < HLM; ++i) {
		if (HT[i].value == 1) ++cnt;
	}

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