[BOJ][C++] 1269 대칭 차집합(feat. 이분탐색)

 

문제 & 설명

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

 

 

풀이

A의 원소 하나하나의 값을 B에서 찾을 때 이분탐색을 진행한다.

---

 

정답 코드

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



int main() {
    int aNum, bNum, input, sum = 0;
    int l, h, mid; // 이분탐색을 위한 변수
    vector<int> As, Bs;

    // Input
    cin >> aNum >> bNum;
    for (int i = 0; i < aNum; i++) {
        cin >> input;
        As.push_back(input);
    }
    for (int i = 0; i < bNum; i++) {
        cin >> input;
        Bs.push_back(input);
    }
    sort(As.begin(), As.end());
    sort(Bs.begin(), Bs.end());

    // Search
    for (int i = 0; i < aNum; i++) {
        l = 0;
        h = bNum;

        while (l <= h) {
            mid = (l + h) / 2;

            if (As[i] == Bs[mid]) {
                As[i] = Bs[mid] = 0;
                break;
            }
            else if (As[i] > Bs[mid]) l = mid + 1;
            else h = mid - 1;
        }
    }

    // Count & Output
    for (int i = 0; i < aNum; i++) {
        if (As[i] > 0) sum += 1;
    }
    for (int i = 0; i < bNum; i++) {
        if (Bs[i] > 0) sum += 1;
    }
    cout << sum << "\n";

    return 0;
}

 

 

시간초과 코드

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



int main() {
	int aNum, bNum, input, searchIndex = 0, sum = 0;
	vector<int> As, Bs;

	// Input
	cin >> aNum >> bNum;
	for (int i = 0; i < aNum; i++) {
		cin >> input;
		As.push_back(input);
	}
	for (int i = 0; i < bNum; i++) {
		cin >> input;
		Bs.push_back(input);
	}
	sort(As.begin(), As.end(), greater<int>());
	sort(Bs.begin(), Bs.end(), greater<int>());

	// Search
	searchIndex = 0;
	for (int i = 0; i < aNum; i++) {
		for (int j = searchIndex; j < bNum; j++) {
			if (As[i] > Bs[j]) break;
			if (As[i] == Bs[j]) {
				As[i] = Bs[j] = 0;
				searchIndex = j + 1;
				break;
			}
		}
	}

	// Count & Output
	for (int i = 0; i < aNum; i++) {
		if (As[i] > 0) sum += 1;
	}
	for (int i = 0; i < bNum; i++) {
		if (Bs[i] > 0) sum += 1;
	}
	cout << sum << "\n";

	return 0;
}