[백준 1269] 대칭 차집합

 

 

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

1269번: 대칭 차집합

 

원소가 있는지 없는지를 빠르게 체크하기 위해서 map을 사용했다.

c++의 map은 레드블랙트리라는 Binary Search Tree로 구현되어 있기 때문에

원소를 찾는데 있어서 O(lgn)의 시간이 걸린다.

 

#include <iostream>
#include <map>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int aSize, bSize;
    map<int, int> a, b;
    
    cin >> aSize >> bSize;
    
    for(int i = 0; i < aSize; i++){
        int temp;
        cin >> temp;
        a[temp] = temp;
    }
    
    for(int i = 0; i < bSize; i++){
        int temp;
        cin >> temp;
        b[temp] = temp;
    }
    
    // a에는 있고 b에는 없는 수 세기
    int sum = 0;
    for(map<int, int>::iterator it = a.begin(); it != a.end(); it++){
        if(!b[it->first])
            sum++;
    }
    
    // b에는 있고 a에는 없는 수 세기
    for(map<int, int>::iterator it = b.begin(); it != b.end(); it++){
        if(!a[it->first])
            sum++;
    }
    
    cout << sum << '\n';
    
    return 0;
}

 

 

 

인터넷을 찾아보니 set으로 푸는게 더 맞는거 같다.... ㅎ.