[코딩테스트] 백준 1269 번 대칭차집합- c++

백준 1269번 대칭 차집합 문제 바로가기

문제 풀이

본 문제는 두 집합에서 교집합이 되는 부분의 개수를 제거한 대칭 차집합의 개수를 구하는 문제이다.
각 집합의 겹치는 부분을 조사해야한다. 이는 각 집합을sorting을 하고, bin search로 진행하면 된다.
더 작은 숫자를 가지고 있는 집합을 기준으로 다른 집합에 그 수를 보유하고 있는지 확인해주었다.

C++ 코드

#include <iostream>
#include <algorithm>

using namespace std; 
bool bin_search(int* a,int val, int left, int right){
    int mid = (left+right)/2; 
    if(a[mid]>val){
        right = mid -1; 
        if(right >= left)
            return bin_search(a,val, left, right);

    }else if(a[mid]<val){
        left = mid+1; 
        if(left <= right)
            return bin_search(a,val, left, right);
    }else{
        return true;
    }
    return false; 
}

int main(){

    int num_A, num_B; //집합 원소 개 
    int* set_A; 
    int* set_B; 

    cin>> num_A>>num_B;
    set_A = new int[num_A];
    set_B = new int[num_B];

    for(int i = 0; i < num_A ; i ++)  
        cin>>set_A[i];
    for(int j = 0 ; j < num_B ; j++)
        cin>>set_B[j];

    sort(set_A, set_A+num_A);
    sort(set_B, set_B+num_B);

    if(num_B < num_A){
        for(int i = 0 ; i < num_B; i ++){
            if (bin_search(set_A,set_B[i],0,num_A)==true)
                union_num ++; 
        }
    }else{
        for(int i = 0 ; i < num_A;i++){
            if(bin_search(set_B,set_A[i],0,num_B)==true)
                union_num ++;
        }
    }

    cout<<num_A+ num_B - union_num*2<<"\n";

    return 0; 
}