[1269번] 대칭 차집합

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 대칭 차집합

2. 정렬

3. 이진 탐색(Binary Search) :: http://www.crocus.co.kr/230

대칭 차집합에 대한 정의는 문제에 서술 되어있고

이 정의를 이용하여 이진 탐색을 기반으로 문제를 해결한다.

이진 탐색이 아닌 일반 탐색으로 2중 포문을 이용하면 O(n^2)의 시간복잡도로 TLE(Time Limit Exceeded)가 발생한다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

#include <iostream> #include <cstdio> #include <algorithm>   using namespace std;   int a[200002]; int b[200002];   int A_binarysearch(int start, int end, int target) {     int mid;     while (start <= end)     {         mid = (start + end) / 2;           if (target == b[mid])             return 1;           else             target > b[mid] ? start = mid + 1 : end = mid - 1;     }     return 0; }   int B_binarysearch(int start, int end, int target) {     int mid;     while (start <= end)     {         mid = (start + end) / 2;           if (target == a[mid])             return 1;           else             target > a[mid] ? start = mid + 1 : end = mid - 1;     }     return 0; }   int main() {     int na, nb;     int cnt = 0;     int ans = 0;       scanf("%d %d", &na, &nb);       for (int i = 0; i < na; i++)         scanf("%d", &a[i]);       for (int i = 0; i < nb; i++)         scanf("%d", &b[i]);       // 이진 탐색을 위해 a와 b를 정렬한다.     sort(a, a + na);     sort(b, b + nb);            for (int i = 0; i < na; i++)         cnt += A_binarysearch(0, nb - 1, a[i]);       // b - a를 하였을 때 남는 것을 ans에 넣는다.     ans = nb - cnt;     cnt = 0;       for (int i = 0; i < nb; i++)         cnt += B_binarysearch(0, na - 1, b[i]);       // a - b를 하였을 때 남는 것을 ans에 넣는다.     ans = ans + na - cnt;       printf("%d", ans);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus