[이진탐색] 1269번 대칭 차집합

처음에 원소의 개수가 20만을 넘지 않는다는걸 원소의 값이 20만이 넘지 않는다는걸로 착각해서 약간 삽질을 좀 했다.

이 문제를 풀려면 O(nlogn)방식을 사용해야 한다. 왜냐하면 원소의 개수가 20만개 까지가능하기 때문에 O(n^2)을 쓰면 시간초과가 난다.

이 문제를 풀면서 벡터에 push_back연산이 얼마나 느린지를 깨달았다.

처음에 벡터를 통해서 문제를 풀었는데 똑같은 코드인데 벡터는 시간초과가 나고 배열로 풀었을땐 시간초과가 나지 않았다 내생각에는 입력을 받을때 벡터로 받게 되면 벡터는 연속적인 메모리 공간에 값을 나란히 저장하므로, 벡터가 처음에 할당한 크기를 넘어서는 입력이 들어오게 되면 메모리를 재 할당하기 때문에 굉장히 시간이 오래걸릴수 있는 연산이 바로 push_back연산이다.

우선 1 2 4 각각의 숫자에 대하여 2 3 4 5 6 에 각 숫자가 있는지 없는지 판단해서 없는경우 결과값에 1을 더해준다.

마찬가지로 2 3 4 5 6 의 각각 숫자에 대해 1 2 4에 그 값이 있는지 없는지 판단해서 없는 경우 결과값에 1을 더해주는 식으로 알고리즘을 구현했다.

그 값이 어떤 배열에 있는지 없는지 찾기 위해서는 선형탐색을 할수 있지만 이렇게 할경우 O(n)이므로 문제의 조건을 만족 시킬수 없다 따라서 좀더 빠른 탐색을 위해서 O(logn) 방식 탐색인 이진 탐색을 활용 했다.

각각의 숫자에 대해서 이진탐색을 하므로 n * logn 방식이 되고 이 방식은 위의 시간제한을 통과할수 있다.

https://www.youtube.com/watch?v=SKcG0p73yo4 ->이진탐색 설명

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m,result;
int v1[200001];
int v2[200001];
 
int binarysearch(int* v,int len,int key) { //찾으려고 하는 key의 인덱스 리턴
    int left = 0;
    int right = len - 1;
    int mid = 0;
 
    while (left <= right) {
        mid = (right + left) / 2;
        if (v[mid] == key)
            return mid;
        else
        {
            if (key > v[mid])
                left = mid + 1;
            else if (key < v[mid])
                right = mid - 1;
        }
    }
    return -1;
}
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        scanf("%d", &v1[i]);
    for (int i = 0; i < m; i++)
        scanf("%d", &v2[i]);
    sort(v1, v1+n);
    sort(v2, v2+m); //시간복잡도 O(nlogn)
    int result = 0;
    for (int i = 0; i < n; i++) { //시간복잡도 O(n)
        if(binarysearch(v2, m,v1[i]) == -1) result++; //시간복잡도 O(logn)
    }// 시간복잡도 O(nlogn)
 
    for (int j = 0; j < m; j++) { //시간복잡도 O(n)
        if (binarysearch(v1,n,v2[j]) == -1) result++; //시간복잡도 O(logn)
    }// 시간복잡도 O(nlogn)
    
    printf("%d\n", result);
 
 
    return 0;
}