문제 링크: https://www.acmicpc.net/problem/1269
투포인터로 풀 수 있습니다.
두 배열을 정렬한 뒤, 0번 인덱스부터 두 개씩 비교합니다. 배열의 값이 같으면 두 포인터를 모두 1씩 +하고, 배열의 값이 다르면 작은 배열의 포인터를 + 해줍니다.
배열의 값이 같은 회수를 세면 그것이 교집합의 원소 개수가 됩니다. 따라서 답은 a의 원소 개수 + b의 원소 개수 - 2 * 교집합 원소의 개수가 됩니다
#pragma GCC optimize ("Ofast")
#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#include <bits/stdc++.h>
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> va(n);
for (auto& c : va)
cin >> c;
vector<int> vb(m);
for (auto& c : vb)
cin >> c;
sort(va.begin(), va.end());
sort(vb.begin(), vb.end());
int counter = 0;
int p1 = 0, p2 = 0;
while (p1 < n && p2 < m) {
if (va[p1] == vb[p2]) {
++p1, ++p2;
++counter;
}
else if (va[p1] < vb[p2]) {
++p1;
}
else {
++p2;
}
}
cout << (n+m) - 2*counter << '\n';
return 0;
}
반응형
'Online Judge > 백준' 카테고리의 다른 글
[백준][C++] 14247: 나무 자르기 (0) | 2020.07.20 |
---|---|
[백준][C++] 1753: 최단경로 (0) | 2020.07.20 |
[백준][C++] 17370: 육각형 우리 속의 개미 (0) | 2020.07.19 |
[백준][C++] 18917: 수열과 쿼리 38 (0) | 2020.07.18 |
[백준][C++] 1072: 게임 (0) | 2020.07.18 |