[C++] 백준 1822번 차집합

1. 문제이해

1822번: 차집합 (acmicpc.net)

1822번: 차집합

 

먼저, 집합 A의 원소의 개수, 집합 B의 원소의 개수를 입력받는다.

입력받은 원소의 개수만큼 원소를 입력받은 후,

A의 원소 중 B의 원소가 아닌 것의 개수와 구체적인 원소를 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

A의 원소 중 B가 아닌 원소들, 즉 문제 제목과 같이 차집합, A - B를 구하면 되는 문제이다.

단순해보이는 문제이지만 개인적으로 정말 많은 시간이 걸린 문제였다.😰

처음에는 단순히 for문을 통해 A의 원소와 B의 원소를 비교해 차집합을 구하는 방식을 사용했지만,

역시나 시간에 민감한 백준에서는 시간초과가 났다.

따라서 저번 포스팅에서 사용했던 이진트리를 이용해 코드를 구현해보았지만, 그마저도 에러가 났다.

시간초과가 아닌 단순 에러였지만 어디가 잘못된건지를 찾지 못해서 다른 방법을 강구했다.

 

결국 마지막 선택지로 선택한것이 바로 set container였다.

블로그 포스팅을 하면서 set는 처음 써보는 것 같은데, set를 사용하니 확실히 훨씬 구현히 편했다.

 

set의 특징은 다음과 같다.

1. key라 불리는 원소들의 집합으로,

2. key값은 중복이 허용되지 않으며,

3. 삽입이 되면 자동으로 정렬

또한, 균형 이진트리의 구조로 구현이 되어있어, 이진트리 대신 사용이 가능하다.

(중위순회를 통해 순서대로 출력)

set의 사용법은 다음과 같다.

 

1. set < [Data Type] > [변수이름]; 형태로 선언

ex) set <int> s;

 

2. s.begin();
 :맨 첫번째 원소를 가리키는 반복자를 리턴(참조)한다.

 

3. s.end();
: 맨 마지막 원소(의 다음)를 가리키는 원소의 끝부분을 알 때 사용한다.
: 반복자를 리턴(참조)합니다.

 

4. s.insert(k);
: 원소 k를 삽입하며, 삽입시 자동으로 정렬된 위치에 삽입된다.

5. s.erase(iter);
: iter가 가리키는 원소를 제거한다
: 제거 한다음 제거 한 원소 다음 원소를 가리키는 반복자를 리턴한다.

 

6. s.find(k);
: 원소 k를 가리키는 반복자를 반환한다.
: 원소 k가 없다면 s.end() 와 같은 반복자를 반환한다.

 

7. s.size();
: 사이즈(원소의 갯수)를 반환한다.

 

 

set에 대한 더 자세한 설명은 아래 블로그를 참고하도록 하자.

https://blockdmask.tistory.com/79

[C++] set container 정리 및 사용법

 

 

 

3. 소스코드

#include <iostream>
#include <set>

using namespace std;

set<int> s;
set<int>::iterator check;
set<int>::iterator t;

int main(void) {
	int A, B;
	int setA;
	int setB;
	cin >> A >> B;

	for (int i = 0; i < A; i++) {
		cin >> setA;
		s.insert(setA);
	}

	for (int i = 0; i < B; i++)	{
		cin >> setB;

		// B의 원소가 A에 있는지 확인
		check = s.find(setB);

		// 끝까지 없으면 다음 원소 입력받아 확인
		if (check == s.end()) {
			continue;
		}
		// 있으면 해당 원소 A에서 지워주기
		else {
			s.erase(check);
		}
	}

	cout << s.size() << "\n";
	
	// A-B 출력
	for (t = s.begin(); t != s.end(); t++) {
		cout << *t << " ";
	}

	cout << "\n";

	return 0;
}

set를 이용해 A - B 차집합을 구현해주었다.

먼저 set의 원소에 하나씩 접근하기 위해 iterator 2개를 선언해주었다.

(각각 check, t로, check는 B의 원소가 A에 있는지 확인할때,

즉, 입력받은 B가 set에 있는지 확인하기 위해 사용하고, t는 for문에서 사용한다.)

 

A와 B의 원소의 개수를 입력받은 뒤, 해당 개수만큼 A의 원소를 입력받고,

이를 insert를 통해 자동으로 정렬된 위치에 삽입해준다.

 

이후 B의 원소를 하나씩 입력받을때마다 해당 원소가 정렬된 set에 있는지(A에 있는지)를 판단,

없으면 s. end를 반환하므로, check == s.end이면 해당 원소는 건너뛰고 다음 원소를 입력받는다.

만약 있다면 해당 원소를 set에서(A에서) 지우고 다음 원소를 입력받는다.

 

위와 같은 과정을 거치고 나면, set에는 A - B에 해당하는 원소들만 남게되므로,

set의 사이즈를 출력하고, set의 원소들을 출력한다.

 

 

---

개인적으로 나에게는 너무 어려웠다...😭

set을 사용하던 사람이거나 파이썬을 이용하는 사람이라면 쉽게 구현이 가능했을것같다.

(실제로 찾아보니 파이썬은 그냥 A-B하면 끝나더라...)

그래도, set은 자주 사용하지 않아서 이번 기회로 다시 한번 되새긴 것 같아 뿌듯하다.

다음번에는 이런 방법도 염두에 두고 다양하게 문제를 풀어봐야겠다.