[C++] 백준 1269: 대칭 차집합

문제 이해

- 자연수를 원소로 갖는 공집합이 아닌 집합 A와 B가 있다.

- 대칭 차집합: (A - B) U (B - A)

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 256MB

 

<입력>

- 집합 A와 B의 원소의 개수 (1 ~ 200,000, 10^5)

- 집합 A와 B의 원소의 값들 (1 ~ 100,000,000, 10^8)

 

<출력>

- 두 집합의 대칭 차집합의 개수를 출력하라.

 

 

문제 풀이

A * B의 시간 복잡도는 O(N^2)이 되어 시간초과이다.

그러므로 당연히 완전 탐색은 아니었고,

 

처음에 시도한 방법은 이분 탐색이었다.

 

A와 B의 원소의 개수의 합을 미리 초기화해둔 뒤

 

A의 원소만 배열에 넣어두고,

B의 원소를 입력받을 때 존재할경우 합에서 -2씩 해준뒤 그 값을 출력해줬다.

 

이 방법으로도 AC를 받기는 했지만, 문제 알고리즘을 보니 맵(map)을 사용하는 방법도 있었다.

 

 

맵을 사용하는 방식은

map<int, bool>으로 선언해준 뒤,

a와 b를 합쳐서 입력받는다.

 

그 후, 값이 없을경우 true로

있을 경우 삭제하는 방식으로 진행한 뒤 그 사이즈를 출력해주는 것이다.

 

int형의 인덱스로 바로 참조가 가능하다는 점을 이용한 거 같은데 꽤나 신박했다.

 

 

전체 코드

1. 이분 탐색

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int a, b;
int num[200005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>a>>b;
    for(int i = 0; i < a; i++){
        cin>>num[i];
    }

    sort(num, num+a);

    int sum = a+b;
    while(b--){
        int tmp;
        cin>>tmp;

        int upperIdx = upper_bound(num, num+a, tmp) - num;
        int lowerIdx = lower_bound(num, num+a, tmp) - num;
        if(upperIdx - lowerIdx > 0){ //있을경우
            sum -= 2;
        }
    }

    cout<<sum;
    return 0;
}

 

 

2. 자료구조(map)의 이용

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
using namespace std;

int a, b;
map <int, bool> num;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>a>>b;
    for(int i = 0; i < a+b; i++){
        int tmp;
        cin>>tmp;

        if(num[tmp] == true){
            num.erase(tmp);
        }else{
            num[tmp] = true;
        }
    }

    cout<<num.size();
    return 0;
}

map의 사용법에 대해 익힐 수 있었던 문제였다!