백준1269번 대칭 차집합(Symmetric Difference) C++로 구현해보기

---

 

```

백준1269번 대칭 차집합(Symmetric Difference) C++로 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 1269번 풀이

---

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

1269번: 대칭 차집합

 

 

백준 1269번 대칭 차집합은 난이도 쉬움 등급의 문제로서

 

두 집합의 대칭 차집합원소의 개수를 구하는 문제입니다.

 

대칭 차집합을 처음 듣는 분들은 아래 벤다이어그램 에서 오렌지 색 영역의 원소를 구하면 된다고 생각하시면 됩니다.

 

대칭 차집합 그림

 

자 그럼~

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

일단 저는 

 

A의 전체 원소를 구하고

B의 전체 원소를 구한다음

 

각 원소를 오름차순으로 정렬해주고

 

교집합을 구해준 다음

 

A와 B를 더한 원소들에서 에서 A와 B의 교집합을 두번 빼줘서 구했습니다.

 

 

설명을 하자면 이번에도 클래스를 선언해주고

class CTwoSets {
private:
	vector<int> setA;
	vector<int> setB;
	int sizeA;
	int sizeB;

public:
	CTwoSets(const int sizeA, const int sizeB)
	{
		this->sizeA = sizeA;
		this->sizeB = sizeB;
	}
	~CTwoSets()
	{
	}

	void insertElementToA(const int elem)
	{
		setA.push_back(elem);
	}
	
	void insertElementToB(const int elem)
	{
		setB.push_back(elem);
	}

	void sortSetA()
	{
		sort(setA.begin(), setA.end());
	}

	void sortSetB()
	{
		sort(setB.begin(), setB.end());
	}

	void printNumberOfElementsInSymmetricDifference()
	{
		int counter = 0;
		int indexA = 0;
		int indexB = 0;

		while (indexA < sizeA && indexB < sizeB)
		{
			if (setA[indexA] == setB[indexB])
			{
				indexA++;
				indexB++;
				counter++;
			}

			else if (setA[indexA] < setB[indexB])
			{
				indexA++;
			}

			else
			{
				indexB++;
			}
		}

		const int result = sizeA + sizeB - (counter * 2);
		printf("%d", result);
	}
};

 

두 집합을 입력 받은 다음

	int A, B;
	scanf("%d %d", &A, &B);

	CTwoSets* cTwoSets = new CTwoSets(A, B);

	for (int i = 0; i < A; i++)
	{
		int tempVal;
		scanf("%d", &tempVal);
		cTwoSets->insertElementToA(tempVal);
	}

	for (int i = 0; i < B; i++)
	{
		int tempVal;
		scanf("%d", &tempVal);
		cTwoSets->insertElementToB(tempVal);
	}

두 집합을 각각 정렬 해주고

	cTwoSets->sortSetA();
	cTwoSets->sortSetB();

두 집합의 대칭 차집합의 원소를 구했습니다.

cTwoSets->printNumberOfElementsInSymmetricDifference();

오름차순으로 정렬되있기 때문에

 

원소가 같으면 교집합에 1을 더하고 인덱스를 각 1씩 더해주고

원소가 다른 경우

집합 A 가 B 보다 더 크면 A의 인덱스에 1을 더하고

집합 B 가 A 보다 더 크면 B의 인덱스에 1을 더하는 방법으로

 

교집합의 원소의 수를 구한 다음

 

A의 크기 + B의 크기에서 교집합 곱하기 2를 빼주고 그 수를 출력해주었습니다.

	void printNumberOfElementsInSymmetricDifference()
	{
		int counter = 0;
		int indexA = 0;
		int indexB = 0;

		while (indexA < sizeA && indexB < sizeB)
		{
			if (setA[indexA] == setB[indexB])
			{
				indexA++;
				indexB++;
				counter++;
			}

			else if (setA[indexA] < setB[indexB])
			{
				indexA++;
			}

			else
			{
				indexB++;
			}
		}

		const int result = sizeA + sizeB - (counter * 2);
		printf("%d", result);
	}

 

전체 코드는 아래와 같습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

#pragma warning(disable : 4996)


class CTwoSets {
private:
	vector<int> setA;
	vector<int> setB;
	int sizeA;
	int sizeB;

public:
	CTwoSets(const int sizeA, const int sizeB)
	{
		this->sizeA = sizeA;
		this->sizeB = sizeB;
	}
	~CTwoSets()
	{
	}

	void insertElementToA(const int elem)
	{
		setA.push_back(elem);
	}
	
	void insertElementToB(const int elem)
	{
		setB.push_back(elem);
	}

	void sortSetA()
	{
		sort(setA.begin(), setA.end());
	}

	void sortSetB()
	{
		sort(setB.begin(), setB.end());
	}

	void printNumberOfElementsInSymmetricDifference()
	{
		int counter = 0;
		int indexA = 0;
		int indexB = 0;

		while (indexA < sizeA && indexB < sizeB)
		{
			if (setA[indexA] == setB[indexB])
			{
				indexA++;
				indexB++;
				counter++;
			}

			else if (setA[indexA] < setB[indexB])
			{
				indexA++;
			}

			else
			{
				indexB++;
			}
		}

		const int result = sizeA + sizeB - (counter * 2);
		printf("%d", result);
	}
};




int main()
{
	int A, B;
	scanf("%d %d", &A, &B);

	CTwoSets* cTwoSets = new CTwoSets(A, B);

	for (int i = 0; i < A; i++)
	{
		int tempVal;
		scanf("%d", &tempVal);
		cTwoSets->insertElementToA(tempVal);
	}

	for (int i = 0; i < B; i++)
	{
		int tempVal;
		scanf("%d", &tempVal);
		cTwoSets->insertElementToB(tempVal);
	}

	cTwoSets->sortSetA();
	cTwoSets->sortSetB();

	cTwoSets->printNumberOfElementsInSymmetricDifference();

	return 0;
}

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---